Ở đây chúng ta sẽ thấy kỹ thuật quicksort nhưng chúng ta sẽ sử dụng quicksort ba chiều. Kỹ thuật nhanh chóng cơ bản chỉ là tìm một phần tử làm trục xoay, sau đó phân vùng mảng xung quanh trục, sau đó, lặp lại cho các mảng con ở bên trái và bên phải của trục.
Quicksort ba chiều cũng tương tự, nhưng có ba phần. mảng arr [1 đến n] được chia thành ba phần.
- arr [1 đến i]
- arr [i + 1, j]
- arr [j + 1, n]
Thuật toán
phân vùng (arr, left, right, i, j) -
begin if right – left <= 1, then if arr[right] < arr[left], then swap arr[right] and arr[left] i := left j := right return end if mid := left, pivot = arr[right] while mid <= right, do if arr[mid] < pivot, then swap arr[left], arr[mid] increase left and mid by 1 else if arr[mid] = pivot, then increase mid by 1 else swap arr[mid], arr[right] decrease right by 1 done i := left – 1 j := mid end
quicksort (arr, left, right) -
begin if left >= right, then return end if define i and j partition(arr, left, right, i, j) quicksort(arr, left, i) quicksort(arr, j, right) end
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 or 0 elements
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);
} Đầu ra
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