โปรแกรม C++ ใช้ Quick Sort กับข้อมูลจำนวนมาก

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

ที่นี่เราพิจารณาอาร์เรย์ขนาดใหญ่ (เกือบ 100 องค์ประกอบ) เราเอาตัวเลขบางตัวแล้วสลับสุ่มเพื่อทำให้ไม่เรียง แล้วเรียงด้วย quicksort

ความซับซ้อนของเทคนิค 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
    pivot := array[upper]
    i := lower - 1
    for j in range lower ถึง higher ทำ
        ถ้า array[j] < pivot แล้ว
            สลับค่า array[i] และ array[j]
            i := i + 1
        จบ if
    จบ for
    สลับค่า array[upper] และ array[i + 1]
    return i + 1
End

quickSort(array, left, right)

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

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

Begin
    ถ้า lower < right แล้ว
        q = 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;
    }
}

int partion(int arr[], int p, int r) {
    int pivot = arr[r]; // รายการสุดท้ายเป็น pivot
    int i = p - 1;
    for (int j = p; j < r; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i+1], arr[r]);
    return i + 1;
}

void quick_sort(int arr[], int p, int q) {
    // เรียงแบบ recursive
    int j;
    if (p < q) {
        j = partion(arr, p, q);
        quick_sort(arr, p, j - 1);
        quick_sort(arr, j + 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