โปรแกรม C++ Stooge Sort (การเรียงลำดับแบบ Stooge)

ภาพรวม

Stooge Sort เป็นอัลกอริทึมเรียงลำดับแบบ Recursive ที่มีลักษณะเฉพาะตัว: แบ่งอาร์เรย์เป็น 2 ส่วนทับซ้อนกัน (2/3 แต่ละส่วน) และเรียงซ้ำ 3 รอบ (ซ้าย, ขวา, ซ้ายอีกครั้ง) ความซับซ้อนด้านเวลา O(n^log₃/₁.₅) ≈ O(n^2.7095) ช้ากว่า Bubble Sort ใช้เพื่อการศึกษา/ทดสอบเท่านั้น

อัลกอริธึม

1. ถ้าขนาดส่วน ≤ 2: เปรียบเทียบและสลับถ้าจำเป็น
2. คำนวณ temp = (end - start + 1) / 3 (ขนาด 1/3)
3. เรียงส่วนซ้าย 2/3: StoogeSort(arr, start, end - temp)
4. เรียงส่วนขวา 2/3: StoogeSort(arr, start + temp, end)
5. เรียงส่วนซ้าย 2/3 อีกครั้ง: StoogeSort(arr, start, end - temp)

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

#include <iostream>
#include <vector>
using namespace std;

void stoogeSort(vector& arr, int start, int end) {
    if (end - start + 1 <= 2) {
        if (arr[end] < arr[start]) {
            swap(arr[start], arr[end]);
        }
        return;
    }
    
    int temp = (end - start + 1) / 3;
    stoogeSort(arr, start, end - temp);      // ส่วนซ้าย 2/3
    stoogeSort(arr, start + temp, end);      // ส่วนขวา 2/3
    stoogeSort(arr, start, end - temp);      // ส่วนซ้าย 2/3 อีกครั้ง
}

int main() {
    int n;
    cout << "Enter the number of data elements to be sorted: ";
    cin >> n;
    
    vector arr(n);
    for (int i = 0; i < n; i++) {
        cout << "Enter element " << i+1 << ": ";
        cin >> arr[i];
    }
    
    stoogeSort(arr, 0, n-1);
    
    cout << "\nSorted Data: ";
    for (int val : arr) cout << "->" << val;
    return 0;
}

ผลลัพธ์ตัวอย่าง

Enter the number of data elements to be sorted: 4
Enter element 1: 6
Enter element 2: 7
Enter element 3: 3
Enter element 4: 2
Sorted Data: ->2->3->6->7

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

• ความซับซ้อน: T(n) = 3T(2n/3) + O(1) → O(n^log₁.₅3) ≈ O(n^2.7095)
• เปรียบเทียบ: ช้ากว่า Bubble Sort (O(n²)), Insertion Sort (O(n²)), แม้แต่ Bogosort ในบางกรณี
• ใช้ได้เมื่อไหร่: ใช้สำหรับการสอนหลักการ Recursive, การทดสอบเวลา, หรือเพื่อความสนุก ไม่ควรใช้ใน Production
• ชื่อ由来: มาจากทีมตลก "The Three Stooges" ที่ทำซ้ำกัน 3 ครั้ง