Stooge Sort ใน Python

Stooge Sort เป็น Sorting Algorithm แบบ Recursive ที่ไม่ค่อยใช้งานจริง (Complexity สูง) แต่น่าสนใจทางทฤษฎี

อัลกอริทึม

1. ถ้า arr[0] > arr[-1] → Swap
2. Sort 2/3 แรก (Recursive)
3. Sort 2/3 หลัง (Recursive)
4. Sort 2/3 แรกอีกครั้ง (Recursive)

ตัวอย่างโค้ด Python

def stoogesort(arr, l, h):
    if l >= h:
        return
    
    # Swap ถ้าตัวแรก > ตัวสุดท้าย
    if arr[l] > arr[h]:
        arr[l], arr[h] = arr[h], arr[l]
    
    # ถ้ามากกว่า 2 ตัว เรียก Recursive
    if h - l + 1 > 2:
        t = (h - l + 1) // 3
        
        # Sort first 2/3
        stoogesort(arr, l, h - t)
        # Sort last 2/3
        stoogesort(arr, l + t, h)
        # Sort first 2/3 again
        stoogesort(arr, l, h - t)

# ทดสอบ
arr = [1, 4, 2, 3, 6, 5, 8, 7]
n = len(arr)
stoogesort(arr, 0, n - 1)
print("Sorted sequence:", arr)
# Output: [1, 2, 3, 4, 5, 6, 7, 8]

ผลลัพธ์

Sorted sequence is: 1 2 3 4 5 6 7 8

Complexity Analysis

Recurrence: T(n) = 3T(2n/3) + O(1)
By Master Theorem: T(n) = O(n^{log_{1.5} 3}) ≈ O(n^{2.709})

แย่กว่า Bubble Sort (O(n²))!

เมื่อไหร่ใช้?

• การศึกษา/ทฤษฎี Computer Science
• ตัวอย่าง Recursive Algorithm ที่แปลก
• ไม่ควรใช้ใน Production

เปรียบเทียบ: Stooge Sort ช้ากว่า Bubble, Insertion, Selection Sort ทั้งหมด ใช้แค่เพื่อความสนุก/เรียนรู้