QuickSort 3 chiều (Cờ Hà Lan)

Chúng ta sẽ xem kỹ thuật quicksort nhưng dùng quicksort 3 chiều. Quicksort cơ bản chỉ tìm một phần tử làm pivot, phân hoạch mảng quanh pivot, sau đó đệ quy cho mảng con bên trái và bên phải.

Quicksort 3 chiều tương tự nhưng có ba phân đoạn. Mảng arr[1 đến n] chia thành ba phần:

• arr[1 đến i]
• arr[i + 1, j]
• arr[j + 1, n]

Thuật toán

partition(arr, left, right, i, j) -

bắt đầu
    nếu right – left <= 1, thì
        nếu arr[right] < arr[left], thì
            hoán đổi arr[right] và arr[left]
        i := left
        j := right
        trả về
    kết thúc nếu
    mid := left, pivot = arr[right]
    trong khi mid <= right, làm
        nếu arr[mid] < pivot, thì
            hoán đổi arr[left], arr[mid]
            tăng left và mid lên 1
        khác nếu arr[mid] = pivot, thì tăng mid lên 1
        khác
            hoán đổi arr[mid], arr[right]
            giảm right xuống 1
    xong
    i := left – 1
    j := mid
kết thúc

quicksort(arr, left, right) -

bắt đầu
    nếu left >= right, thì
        trả về
    kết thúc nếu
    định nghĩa i và j
    partition(arr, left, right, i, j)
    quicksort(arr, left, i)
    quicksort(arr, j, right)
kết thúc

Ví dụ

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

void partition(int arr[], int left, int right, int &i, int &j) {
    if (right - left <= 1) {
        if (arr[right] < arr[left])
            swap(arr[right], arr[left]);
        i = left;
        j = right;
        return;
    }
    int mid = left;
    int pivot = arr[right];
    while (mid <= right) {
        if (arr[mid] < pivot)
            swap(arr[left++], arr[mid++]);
        else if (arr[mid] == pivot)
            mid++;
        else if (arr[mid] > pivot)
            swap(arr[mid], arr[right--]);
    }
    i = left - 1;
    j = mid;
}

void quicksort(int arr[], int left, int right) {
    if (left >= right) // 1 hoặc 0 phần tử
        return;
    int i, j;
    partition(arr, left, right, i, j);
    quicksort(arr, left, i);
    quicksort(arr, j, right);
}

void display(int arr[], int n) {
    for (int i = 0; i < n; ++i)
        cout << " " << arr[i];
    cout << endl;
}

int main() {
    int a[] = {4, 9, 4, 3, 1, 9, 4, 3, 9, 4, 3, 1, 4};
    int n = sizeof(a) / sizeof(int);
    display(a, n);
    quicksort(a, 0, n - 1);
    display(a, n);
}

Kết quả

4 9 4 3 1 9 4 3 9 4 3 1 4
1 1 3 3 3 4 4 4 4 4 9 9 9