สทูจซอร์ต

สทูจซอร์ต () การจัดเรียงเป็นขั้นตอนการเรียงลำดับแบบทวนซ้ำ (recursive sorting algorithm) โดยมีความซับซ้อนเวลา  และ Stooge Sort เป็นการจัดเรียงข้อมูลของอาเรย์ จากน้อยไปมาก ซึงมีประสิทธิต่ำมากเมื่อเปรียบกับ Merge sort และ Bubble sort เพราะว่า

Stooge sort ซึ่งเขียนแบบ recursive แต่ทำงานช้ากว่าแบบ Merge sort แต่โค้ดของ Stooge sort สั้นกว่ามาก
Stooge sort ทำงานคล้าย ๆ แบบ Bubble sort ซึ่ง Stooge sort ทำงานช้ากว่า

 กระบวนการวิเคราะห์ 

 หาความยาวของอาเรย์
 เลขที่มีค่ามากซึ่งอยู่ด้านซ้าย ให้สลับค่าที่น้อยกว่าซึ่งอยู่ด้านขวา
 ตรวจสอบว่ามีค่า array เหลืออยู่หรือไม่
 ถ้ามี หาตำแหน่งด้านใช้สูตร t = (j-i+1)//3
 เขียนแบบ recursive

 ตัวอย่างโค้ด 
 function stoogesort(array L, i = 0, j = length(L)-1){
     if L[i] > L[j] then
         L[i] ↔ L[j]
     if (j - i + 1) > 2 then
         t = (j - i + 1) / 3
         stoogesort(L, i  , j-t)
         stoogesort(L, i+t, j  )
         stoogesort(L, i  , j-t)
     return L
 }

 ตัวอย่างโค้ด ไพธอน 
def stoogesort(array, left, array_len):
    if array_len is None:
        array_len = len(array) - 1

    if array[array_len] < array[left]:
        array[left] , array[array_len] = array[array_len] , array[left]
        #print(array)

    if array_len - left > 1:
        pos = (array_len - left + 1) // 3
        stoogesort(array, left, array_len - pos) ; stoogesort(array, left + pos, array_len) ; stoogesort(array, left , array_len //2)
        #print(array)
    return array

 ข้อดีและข้อเสีย 
ข้อดี ใช้กระบวนการคิดน้อย และโค้ดมีลักษณะสั้น ไม่ซับซ้อน
ข้อเสีย ที่การทำงานช้าเพราะว่า มีการเรียงค่าเสร็จแล้วแต่ยังทำงานต่อกว่าจะครบจำนวนของค่าตัวเองจนหมด

หมวดหมู่:ขั้นตอนวิธีการเรียงลำดับ