Chương trình C++ thực hiện Quick Sort trên số lượng lớn phần tử

Kỹ thuật quicksort được thực hiện bằng cách tách danh sách thành hai phần. Ban đầu một phần tử chốt (pivot) được chọn bởi thuật toán phân hoạch (partitioning). Phần bên trái của pivot chứa các giá trị nhỏ hơn pivot, và phần bên phải chứa giá trị lớn hơn. Sau khi phân hoạch, từng danh sách riêng biệt được phân hoạch bằng cùng thủ tục.

Ở đây chúng ta xem xét một mảng lớn (gần 100 phần tử) để sắp xếp. Chúng ta lấy một số số sau đó xáo trộn chúng theo thứ tự ngẫu nhiên để làm cho chúng không được sắp xếp. Sau đó sắp xếp bằng kỹ thuật quicksort.

Độ phức tạp của kỹ thuật Quicksort

Độ phức tạp thời gian - O(n log n) cho trường hợp tốt và trung bình, O(n²) cho trường hợp xấu.
Độ phức tạp không gian - O(log n)

Đầu vào - Danh sách không sắp xếp: 90 45 22 11 22 50
Đầu ra - Mảng sau khi sắp xếp: 11 22 22 45 50 90

Thuật toán

partition(array, lower, upper)

Đầu vào - Tập dữ liệu mảng, ranh giới dưới và ranh giới trên

Đầu ra - Pivot ở vị trí đúng

Bắt đầu
    pivot := array[upper]
    i := lower - 1
    Với j trong khoảng lower đến higher, thực hiện
        Nếu array[j] < pivot, thì
            Hoán đổi giá trị của array[i] và array[j]
            i := i + 1
    Kết thúc
    Hoán đổi giá trị của array[upper] và array[i + 1]
    Trả về i + 1
Kết thúc

quickSort(array, left, right)

Đầu vào - Một mảng dữ liệu, và ranh giới dưới và trên của mảng

Đầu ra - Mảng đã sắp xếp

Bắt đầu
    Nếu lower < right thì
        q = partition(array, left, right).
        quickSort(array, left, q-1)
        quickSort(array, q+1, right)
Kết thúc

Mã ví dụ

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

void random_shuffle(int arr[]) { 
    //hàm xáo trộn các phần tử mảng vào vị trí ngẫu nhiên 
    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]; //phần tử cuối làm 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) { 
    //đệ quy sắp xếp danh sách 
    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); //để ngẫu nhiên hóa mảng 
    quick_sort(arr, 0, MAX-1); //sắp xếp các phần tử của mảng 
    for (i = 0; i < MAX; i++) 
        cout << arr[i] << " "; 
    cout << endl; 
    return 0; 
}

Kết quả

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