โปรแกรม C++ ใช้ Quick Sort แบบสุ่ม Pivot (Randomized)

เทคนิค Quicksort ทำงานโดยแยกรายการเป็นสองส่วน เริ่มต้นเลือก pivot element ด้วย partitioning algorithm ส่วนซ้ายของ pivot เก็บค่าที่น้อยกว่า pivot ส่วนขวาเก็บค่าที่มากกว่า หลัง partitioning แล้ว แต่ละส่วนจะถูก partition อีกครั้งด้วยขั้นตอนเดียวกัน

ในกรณีนี้เราเลือก pivot element แบบสุ่ม หลังเลือก pivot แล้ว เราทำ partitioning แล้วเรียงอาร์เรย์แบบ recursive

ความซับซ้อนของเทคนิค Quicksort

• Time Complexity - O(n log n) สำหรับ best case และ average case, O(n²) สำหรับ worst case

• Space Complexity - O(log n)

Input - รายการไม่เรียง: 90 45 22 11 22 50
Output - อาร์เรย์หลังเรียง: 11 22 22 45 50 90

อัลกอริทึม

partition(array, lower, upper)

Input: อาร์เรย์ข้อมูล, ขอบเขตล่างและขอบเขตบน

Output: Pivot ในตำแหน่งที่ถูกต้อง

Begin
    index := lower
    pivot := higher
    for i in range lower ถึง higher ทำ
        ถ้า array[i] < array[pivot] แล้ว
            สลับค่า array[i] และ array[index]
            index := index + 1
        จบ if
    จบ for
    สลับค่า array[pivot] และ array[index]
End

random_pivot_partition(array, lower, upper)

Input: อาร์เรย์ข้อมูล, ขอบเขตล่างและขอบเขตบน

Output: ดัชนีสุดท้ายของ pivot ที่เลือกสุ่ม

Begin
    n := ตัวเลขสุ่ม
    pvt := lower + n mod (upper - lower + 1)
    สลับค่า array[pivot] และ array[upper]
    index := Partition(array, lower, upper)
    return index
End

quickSort(array, left, right)

Input: อาร์เรย์ข้อมูล และขอบเขตล่างและบนของอาร์เรย์

Output: อาร์เรย์ที่เรียงแล้ว

Begin
    ถ้า lower < right แล้ว
        q = random_pivot_partition(array, left, right).
        quickSort(array, left, q-1)
        quickSort(array, q+1, right)
    จบ if
End

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

#include <iostream>
#include <cstdlib>
#include <ctime>
#define MAX 100
using namespace std;

void random_shuffle(int arr[]) {
    // ฟังก์ชันสลับอาร์เรย์ให้สุ่ม
    srand(time(NULL));
    for (int i = MAX - 1; i > 0; i--) {
        int j = rand()%(i + 1);
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

// Partitioning the array on the basis of values at high as pivot value.
int Partition(int a[], int low, int high) {
    int pivot, index, i;
    index = low;
    pivot = high;
    for(i=low; i < high; i++) {
        // หาดัชนีของ pivot
        if(a[i] < a[pivot]) {
            swap(a[i], a[index]);
            index++;
        }
    }
    swap(a[pivot], a[index]);
    return index;
}

int RandomPivotPartition(int a[], int low, int high){
    // การเลือก pivot แบบสุ่ม
    int pvt, n, temp;
    n = rand();
    pvt = low + n%(high-low+1); // สุ่มค่า pivot จาก sub-array
    swap(a[high], a[pvt]);
    return Partition(a, low, high);
}

void quick_sort(int arr[], int p, int q) {
    // เรียงแบบ recursive
    int pindex;
    if(p < q) {
        pindex = RandomPivotPartition(arr, p, q); // เลือก pivot แบบสุ่ม
        // ใช้ QuickSort แบบ recursive
        quick_sort(arr, p, pindex-1);
        quick_sort(arr, pindex+1, q);
    }
}

int main() {
    int i;
    int arr[MAX];
    for (i = 0;i < MAX; i++)
        arr[i] = i + 1;
    random_shuffle(arr); // สลับอาร์เรย์ให้สุ่ม
    quick_sort(arr, 0, MAX - 1); // เรียงองค์ประกอบอาร์เรย์
    for (i = 0; i < MAX; i++)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}

ผลลัพธ์

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100