สทูจซอร์ต

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

สทูจซอร์ต

การแสดงให้เห็นสทูจซอร์ต (แสดงเฉพาะการสลับที่)
ประเภท	ขั้นตอนวิธีการเรียงลำดับ
โครงสร้างข้อมูล	Array
ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด	O(n^log 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 

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

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

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