สทูจซอร์ต

สทูจซอร์ต (อังกฤษ: stooge sort) การจัดเรียงเป็นขั้นตอนการเรียงลำดับแบบทวนซ้ำ (recursive sorting algorithm) โดยมีความซับซ้อนเวลา O(n^{log 3 / log 1.5} ) = O(n^2.7095...) และ Stooge Sort เป็นการจัดเรียงข้อมูลของอาเรย์ จากน้อยไปมาก ซึงมีประสิทธิต่ำมากเมื่อเปรียบกับ Merge sort และ Bubble sort เพราะว่า

สทูจซอร์ต

การแสดงให้เห็นสทูจซอร์ต (แสดงเฉพาะการสลับที่)
ประเภท	ขั้นตอนวิธีการเรียงลำดับ
โครงสร้างข้อมูล	Array
ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด	O(nlog 3 /log 1.5)
ปริมาณความต้องการพื้นที่เมื่อเกิดกรณีแย่ที่สุด	O(n)

1.  Stooge sort ซึ่งเขียนแบบ recursive แต่ทำงานช้ากว่าแบบ Merge sort  แต่โค้ดของ Stooge sort

        สั้นกว่ามาก

2. Stooge sort ทำงานคล้าย ๆ แบบ Bubble sort ซึ่ง Stooge sort ทำงานช้ากว่า

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

1. หาความยาวของอาเรย์
2. เลขที่มีค่ามากซึ่งอยู่ด้านซ้าย ให้สลับค่าที่น้อยกว่าซึ่งอยู่ด้านขวา
3. ตรวจสอบว่ามีค่า array เหลืออยู่หรือไม่
4. ถ้ามี หาตำแหน่งด้านใช้สูตร t = (j-i+1)//3
5. เขียนแบบ 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

ข้อดีและข้อเสีย

ข้อดี ใช้กระบวนการคิดน้อย และโค้ดมีลักษณะสั้น ไม่ซับซ้อน

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