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. 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.
Trong trường hợp này, chúng ta chọn phần tử chốt ngẫu nhiên. Sau khi chọn pivot, chúng ta thực hiện phân hoạch, sau đó sắp xếp mảng đệ quy.
Độ 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
index := lower
pivot := higher
Với i trong khoảng lower đến higher, thực hiện
Nếu array[i] < array[pivot], thì
Hoán đổi giá trị của array[i] và array[index]
index := index + 1
Kết thúc
Hoán đổi giá trị của array[pivot] và array[index]
Kết thúcrandom_pivot_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 - Chỉ số cuối cùng của pivot được chọn ngẫu nhiên
Bắt đầu
n := một số ngẫu nhiên
pvt := lower + n mod (upper - lower + 1)
Hoán đổi giá trị của array[pivot] và array[upper]
index := Partition(array, lower, upper)
Trả về index
Kết thúcquickSort(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 = random_pivot_partition(array, left, right).
quickSort(array, left, q-1)
quickSort(array, q+1, right)
Kết thúcMã 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;
}
}
// Phân hoạch mảng dựa trên giá trị tại high làm pivot.
int Partition(int a[], int low, int high) {
int pivot, index, i;
index = low;
pivot = high;
for(i = low; i < high; i++) {
// tìm chỉ số của 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){
// Chọn pivot ngẫu nhiên.
int pvt, n, temp;
n = rand();
pvt = low + n % (high - low + 1); // Ngẫu nhiên hóa giá trị pivot từ mảng con.
swap(a[high], a[pvt]);
return Partition(a, low, high);
}
void quick_sort(int arr[], int p, int q) {
//đệ quy sắp xếp danh sách
int pindex;
if(p < q) {
pindex = RandomPivotPartition(arr, p, q); //chọn pivot ngẫu nhiên
// Đệ quy triển khai QuickSort.
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); //Để 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