โปรแกรม C++ Quick Sort แบบ Randomized Pivot

ภาพรวม

Quick Sort แบบ Randomized Pivot เป็นการปรับปรุง Quick Sort ธรรมดาโดยเลือก Pivot แบบสุ่ม ลดโอกาสเกิด Worst Case O(n²) เมื่อข้อมูลเรียงลำดับหรือเกือบเรียงลำดับ ความซับซ้อนเฉลี่ย O(n log n)

อัลกอริธึม

Partition (Lomuto Partition Scheme)

1. เลือก Pivot (ในที่นี้คือองค์ประกอบสุดท้ายหลังสุ่ม)
2. กำหนด index = low
3. วนลูป i = low ถึง high-1:
   • ถ้า arr[i] < pivot สลับ arr[i] กับ arr[index] เพิ่ม index
4. สลับ arr[index] กับ pivot คืนค่า index

Randomized Pivot Partition

1. สุ่มดัชนี pivotIdx = low + rand() % (high - low + 1)
2. สลับ arr[pivotIdx] กับ arr[high]
3. เรียก Partition(arr, low, high)

QuickSort

1. ถ้า low < high:
   • pivotIndex = RandomPivotPartition(arr, low, high)
   • เรียกซ้ำ QuickSort(arr, low, pivotIndex-1)
   • เรียกซ้ำ QuickSort(arr, pivotIndex+1, high)

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

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

void swap(int& a, int& b) {
    int temp = a; a = b; b = temp;
}

int partition(vector& arr, int low, int high) {
    int pivot = arr[high];
    int index = low;
    
    for (int i = low; i < high; i++) {
        if (arr[i] < pivot) {
            swap(arr[i], arr[index]);
            index++;
        }
    }
    swap(arr[index], arr[high]);
    return index;
}

int randomPivotPartition(vector& arr, int low, int high) {
    int pivotIdx = low + rand() % (high - low + 1);
    swap(arr[pivotIdx], arr[high]);
    return partition(arr, low, high);
}

void quickSort(vector& arr, int low, int high) {
    if (low < high) {
        int pivotIndex = randomPivotPartition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

int main() {
    srand(time(0)); // Seed สำหรับสุ่ม
    
    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];
    }
    
    quickSort(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: 3
Enter element 2: 4
Enter element 3: 7
Enter element 4: 6
Sorted Data: ->3->4->6->7

ข้อดีของ Randomized QuickSort

• หลีกเลี่ยง Worst Case O(n²) บนข้อมูลเรียงลำดับ/เกือบเรียงลำดับ
• คาดหวังเวลา O(n log n) สำหรับทุกประเภทข้อมูล
• ไม่ต้องใช้พื้นที่เพิ่มเติม (In-place) ยกเว้น Stack สำหรับ Recursion
• Cache-friendly เนื่องจากเข้าถึงหน่วยความจำแบบ Sequential