Quicksort là một kỹ thuật sắp xếp sử dụng các phép so sánh để sắp xếp một danh sách (mảng) chưa được sắp xếp. Quicksort còn được gọi là sắp xếp trao đổi phân vùng.
Nó không phải là một sắp xếp ổn định, Bởi vì thứ tự tương đối của các mục sắp xếp bằng nhau không được bảo toàn. Quicksort có thể hoạt động trên một mảng, yêu cầu một lượng nhỏ bộ nhớ bổ sung để thực hiện việc sắp xếp. Nó rất giống với sắp xếp lựa chọn, ngoại trừ việc nó không phải lúc nào cũng chọn phân vùng trường hợp xấu nhất. Vì vậy, chúng tôi có thể coi nó như một hình thức tốt hơn của Sắp xếp lựa chọn.
QuickSort là một trong những thuật toán sắp xếp hiệu quả nhất và dựa trên việc chia mảng thành những mảng nhỏ hơn. Tên gọi này xuất phát từ thực tế là quicksort có khả năng sắp xếp danh sách các phần tử dữ liệu nhanh hơn đáng kể so với bất kỳ thuật toán sắp xếp thông thường nào. Và giống như Sắp xếp hợp nhất, Sắp xếp nhanh cũng thuộc loại phân chia và cách tiếp cận của phương pháp giải quyết vấn đề.
Thuật toán Quicksort hoạt động theo cách sau
-
Theo quan điểm loại suy, hãy xem xét một tình huống mà người ta phải sắp xếp các giấy tờ có tên của học sinh, theo tên. Người ta có thể sử dụng cách tiếp cận như sau -
-
Chọn một giá trị phân tách, chẳng hạn L. Giá trị phân tách còn được gọi là Xoay vòng.
-
Chia chồng giấy thành hai. A-L và M-Z. Không nhất thiết các cọc phải bằng nhau.
-
Lặp lại hai bước trên với cọc A-L, chia nó thành hai nửa đáng kể. Và đống M-Z, chia thành hai nửa của nó. Quá trình này được lặp lại cho đến khi các đống đủ nhỏ để dễ dàng phân loại.
-
Cuối cùng, các cọc nhỏ hơn có thể được đặt chồng lên nhau để tạo ra một bộ giấy tờ được sắp xếp và sắp xếp đầy đủ.
-
-
Phương pháp được sử dụng ở đây là đệ quy ở mỗi lần tách để đến mảng một phần tử.
-
Tại mỗi lần tách, cọc được chia ra và sau đó áp dụng phương pháp tương tự cho các cọc nhỏ hơn.
-
Do những tính năng này, quicksort còn được gọi là phân loại trao đổi phân vùng .
Input: arr[] = {7,4,2,6,3,1,5}
Output: 1 2 3 4 5 6 7 Giải thích
Một ví dụ có thể hữu ích để hiểu khái niệm này. Hãy xem xét mảng sau:50, 23, 9, 18, 61, 32
Bước 1 - Quyết định bất kỳ giá trị nào làm trục từ danh sách (thường là giá trị cuối cùng). Giả sử cho hai giá trị "Thấp" và "Cao" tương ứng với chỉ mục đầu tiên và chỉ mục cuối cùng.
Trong trường hợp của chúng tôi, mức thấp là 0 và mức cao là 5.
Các giá trị ở mức thấp và cao là 50 và 32 và Giá trị của trục là 32.
Do đó, yêu cầu phân vùng, sắp xếp lại mảng theo cách mà trục xoay (32) đến vị trí thực của nó. Và ở bên trái của trục, mảng có tất cả các phần tử nhỏ hơn nó và ở bên phải lớn hơn nó.
Trong chức năng phân vùng, chúng tôi bắt đầu từ phần tử đầu tiên và so sánh nó với pivot. Vì 50 lớn hơn 32, chúng tôi không thực hiện bất kỳ thay đổi nào và chuyển sang phần tử tiếp theo 23.
So sánh lại với trục. Vì 23 nhỏ hơn 32, chúng ta hoán đổi 50 và 23. Mảng trở thành 23, 50, 9, 18, 61, 32.
Chúng tôi chuyển sang phần tử tiếp theo 9 một lần nữa nhỏ hơn pivot (32), do đó hoán đổi nó với 50 làm cho mảng của chúng tôi là
23, 9, 50, 18, 61, 32.
Tương tự, đối với phần tử tiếp theo 18 nhỏ hơn 32, mảng sẽ trở thành
23, 9, 18, 50, 61, 32 Bây giờ 61 lớn hơn trục (32), do đó không có thay đổi.
Cuối cùng, chúng tôi hoán đổi trục xoay của mình với 50 để nó đến đúng vị trí.
Do đó trục xoay (32) đến ở vị trí thực của nó và tất cả các phần tử ở bên trái của nó nhỏ hơn và tất cả các phần tử ở bên phải đều lớn hơn chính nó.
Bước 2 - Do đó mảng sau bước đầu tiên trở thành
23, 9, 18, 32, 61, 50, lấy 32 làm trục.
Bước 3 - Bây giờ danh sách được chia thành hai phần:
1. Danh sách phụ trước trục:23, 9, 18
2. Danh sách phụ sau trục:61, 50
Bước 4 - Lặp lại các bước cho các danh sách phụ này một lần nữa.
Mảng cuối cùng do đó trở thành 9, 18, 23, 32, 50, 61.
Ví dụ
#include <stdio.h>
void swap(int *a, int *b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
int Partition(int a[], int low, int high) {
int pivot, index, i;
index = low;
pivot = high;
for(i=low; i < high; i++) {
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) {
int pvt, n, temp;
n = rand();
pvt = low + n%(high-low+1);
swap(&a[high], &a[pvt]);
return Partition(a, low, high);
}
int QuickSort(int a[], int low, int high) {
return 0;
}
int main() {
int n, i;
n=7;
int arr[]={7,4,2,6,3,1,5};
int high = n-1;
int low = 0 ;
int pindex;
if(low < high) {
pindex = RandomPivotPartition(arr, low, high);
QuickSort(arr, low, pindex-1);
QuickSort(arr, pindex+1, high);
}
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}