Stooge Sort คืออะไร?
O(n^(log 3 / log 1.5)) ≈ O(n^2.7095) - ช้ามาก ใช้เพื่อการศึกษา/ความสนุก ไม่ใช้งานจริง
หลักการ: เรียง 2/3 ส่วนแรก → 2/3 ส่วนหลัง → 2/3 ส่วนแรกอีกครั้ง
ตัวอย่างโค้ด
public class Demo {
static void stoogeSort(int[] arr, int l, int h) {
if (l >= h) return;
// Swap ถ้าตัวแรก > ตัวสุดท้าย
if (arr[l] > arr[h]) {
int temp = arr[l];
arr[l] = arr[h];
arr[h] = temp;
}
// ถ้ามากกว่า 2 elements เรียง recursive
if (h - l + 1 > 2) {
int t = (h - l + 1) / 3;
stoogeSort(arr, l, h - t); // 2/3 ส่วนแรก
stoogeSort(arr, l + t, h); // 2/3 ส่วนหลัง
stoogeSort(arr, l, h - t); // 2/3 ส่วนแรกอีกครั้ง
}
}
public static void main(String[] args) {
int[] arr = {12, 34, 67, 91, 11, 0, 89, 102, 39};
System.out.println("Original: " + Arrays.toString(arr));
stoogeSort(arr, 0, arr.length - 1);
System.out.println("Sorted: " + Arrays.toString(arr));
}
}
ผลลัพธ์
Original: [12, 34, 67, 91, 11, 0, 89, 102, 39] Sorted: [0, 11, 12, 34, 39, 67, 89, 91, 102]
Complexity Analysis
- Time: O(n^2.7095) - ช้ากว่า Bubble Sort (O(n²))!
- Space: O(n) - recursion stack depth
- Stable: ไม่ (swap ตัวแรก/สุดท้ายอาจเปลี่ยนลำดับ equal elements)
เปรียบเทียบ Sorting Algorithms
| Algorithm | Time (Avg) | Time (Worst) | Space | Stable |
|---|---|---|---|---|
| Stooge Sort | O(n^2.71) | O(n^2.71) | O(n) | No |
| Bubble Sort | O(n²) | O(n²) | O(1) | Yes |
| Quick Sort | O(n log n) | O(n²) | O(log n) | No |
| Merge Sort | O(n log n) | O(n log n) | O(n) | Yes |
| Arrays.sort() | O(n log n) | O(n log n) | O(log n) | Yes (objects) |
สรุป: Stooge Sort เป็นตัวอย่าง algorithm ที่ "ทำงานได้แต่ช้ามาก" ใช้สอน recursion และ complexity analysis
