CTDL và giải thuật - Giải thuật Quick Sort
Nhập vào số nguyên dương n
, tiếp theo là n
số nguyên của dãy số a
.
Hãy sắp xếp dãy số a
thành dãy không giảm (số sau không bé hơn số trước) và in dãy đó ra màn hình, sau mỗi phần tử có đúng một khoảng trắng.
Ví dụ:
- Test mẫu 1:
Input Output 5
1 3 2 5 21 2 2 3 5
Vớia = [1, 3, 2, 5, 2]
thì kết quả mong muốn là:
"1 2 2 3 5 ".
- Test mẫu 2:
Input Output 4
3 2 1 41 2 3 4
Vớia = [3, 2, 1, 4
] thì kết quả mong muốn là:
"1 2 3 4 ".
Lý thuyết.
Giới thiệu sắp xếp nhanh (Quick Sort).
Giải thuật sắp xếp nhanh (Quick Sort) là một giải thuật hiệu quả cao và dựa trên việc chia mảng dữa liệu thành các mảng nhỏ hơn. Giải thuật sắp xếp nhanh chia mảng thành hai phần bằng cách so sánh từng phần tử của mảng với một phần tử được chọn gọi là phần tử chốt (Pivot): một mảng bao gồm các phần tử nhỏ hơn hoặc bằng phần tử chốt và mảng còn lại bao gồm các phần tử lớn hơn hoặc bằng phần tử chốt.
Tiến trình chia này diễn ra tiếp tục cho tới khi độ dài của các mảng con đều bằng 1
. Giải thuật sắp xếp nhanh tỏ ra khá hiệu quả với các tập dữ liệu lớn khi mà độ phức tạp trường hợp trung bình và trường hợp xấu nhất là O(nlogn) với n
là số phần tử.
Kỹ thuật chọn phần tử chốt trong giải thuật sắp xếp nhanh (Quick Sort)
Kỹ thuật chọn phần tử chốt ảnh hưởng khá nhiều đến khả năng rơi vào các vòng lặp vô hạn đối với các trường hợp đặc biệt. Tốt nhất là chọn phần tử chốt (pivot) nằm ở trung vị của danh sách. Khi đó, sau log2(n) lần chia chúng ta sẽ đạt tới kích thước các mảng con bằng 1
.
Dưới đây là các cách chọn phần tử chốt:
-
Chọn phần tử đứng đầu hoặc đứng cuối làm phần tử chốt.
-
Chọn phần tử đứng giữa danh sách làm phần tử chốt.
-
Chọn phần tử trung vị trong ba phần tử đứng đầu, đứng giữa và đứng cuối làm phần tử chốt.
-
Chọn phần tử ngẫu nhiên làm phần tử chốt. Tuy nhiên cách này rất dễ dẫn đến khả năng rơi vào các trường hợp đặc biệt.
Cách hoạt động của Quick Sort:
Ví dụ sắp xếp dãy a = [6, 3, 5, 2, 1, 4 , 8, 7]
thành dãy không giảm:
Khởi tạo biến l
và r
là chỉ số đầu và cuối của đoạn cần sắp xếp, khởi tạo l = 0
và r = n-1
.
Xác định phần tử chốt trong dãy p = a[(l+r)/2] = a[3] = 2
.
Sử dụng biến i
và biến j
để chia dãy thành 2
phần. Biến i sẽ chạy từ l
đến r
và biến j
sẽ chạy từ r
về l
. Nếu phát hiện a[i] >= p
và a[j] <= p
thì dừng lại và tráo đổi ví trí của chúng.
while (i < j){
while (a[i] < p){
i++;
}
while (a[j] > p){
j--;
}
if (i <= j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
}
Hình ảnh quá trình thực hiện đến khi i >= j
thì dừng:
Đổi chỗ a[i]
và a[j]
:
Đổi chỗ a[i]
và a[j]
:
Ta thấy i >= j
, ta đã chia dãy dc thành hai phần là:
- Dãy từ
0
đếnj
: Dãy có giá trị nhỏ hơn hoặc bằng phần tử chốt. - Dãy từ
i
đếnn-1
: Dãy có giá trị lớn hơn hoặc bằng phần tử chốt.
Lúc này ta tiếp tục dùng đệ quy để sắp xếp hai dãy đó.
Code mẫu C++:
void quickSort(int a[], int l, int r){
int p = a[(l+r)/2];
int i = l, j = r;
while (i < j){
while (a[i] < p){
i++;
}
while (a[j] > p){
j--;
}
if (i <= j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
}
if (i < r){
quickSort(a, i, r);
}
if (l < j){
quickSort(a, l, j);
}
}
Hướng dẫn bài tập.
Code mẫu:
Ngôn ngữ C++:
#include<iostream>
using namespace std;
void printArray(int a[], int n){
for (int i = 0; i < n; i++){
cout << a[i] << " ";
}
cout << endl;
}
void quickSort(int a[], int l, int r){
int p = a[(l+r)/2];
int i = l, j = r;
while (i < j){
while (a[i] < p){
i++;
}
while (a[j] > p){
j--;
}
if (i <= j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
}
if (i < r){
quickSort(a, i, r);
}
if (l < j){
quickSort(a, l, j);
}
}
int a[100001];
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i++){
cin >> a[i];
}
quickSort(a, 0, n-1);
printArray(a, n);
return 0;
}