สทูจซอร์ต

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

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

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
}

ตัวอย่างโค้ด ไพธอน[แก้]

 1 def stoogesort(array, left, array_len):
 2     if array_len is None:
 3         array_len = len(array) - 1
 4 
 5     if array[array_len] < array[left]:
 6         array[left] , array[array_len] = array[array_len] , array[left]
 7         #print(array)
 8 
 9 
10     if array_len - left > 1:
11         pos = (array_len - left + 1) // 3
12         stoogesort(array, left, array_len - pos) ; stoogesort(array, left + pos, array_len) ; stoogesort(array, left , array_len //2)
13         #print(array)
14     return array

ข้อดีและข้อเสีย[แก้]

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

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