Chào mừng các bạn quay trở lại với blog của Nguyễn Văn Hiếu. Đây là một bài viết trong series các thuật toán sắp xếp có minh họa code sử dụng ngôn ngữ lập trình C++. Ở bài viết này Nguyễn Văn Hiếu xin giới thiệu tới các bạn thuật toán sắp xếp quick sort. Một thuật toán ngay từ cái tên đã cho thấy rằng nó có khả năng sắp xếp với tốc độ cao hơn hẳn so với các thuật toán Insertion sort, selection sort hay bubble sort.
Lưu ý: Bài viết chỉ mô tả cho việc sắp xếp dãy số tăng dần. Việc sắp xếp dãy số giảm dần sẽ tương tự và bạn đọc tự tìm hiểu
NỘI DUNG BÀI VIẾT
- Ý tưởng của thuật toán sắp xếp quick sort
- Minh họa thuật toán sắp xếp quick sort sử dụng ngôn ngữ C++
- Đánh giá thuật toán sắp xếp quick sort
- Tham khảo
Ý tưởng của thuật toán sắp xếp quick sort
Mô phỏng thuật toán sắp xếp quick sort
Giống như Merge sort, thuật toán sắp xếp quick sort là một thuật toán chia để trị( Divide and Conquer algorithm). Nó chọn một phần tử trong mảng làm điểm đánh dấu(pivot). Thuật toán sẽ thực hiện chia mảng thành các mảng con dựa vào pivot đã chọn. Việc lựa chọn pivot ảnh hưởng rất nhiều tới tốc độ sắp xếp. Nhưng máy tính lại không thể biết khi nào thì nên chọn theo cách nào. Dưới đây là một số cách để chọn pivot thường được sử dụng:
- Luôn chọn phần tử đầu tiên của mảng.
- Luôn chọn phần tử cuối cùng của mảng. (Được sử dụng trong bài viết này)
- Chọn một phần tử random.
- Chọn một phần tử có giá trị nằm giữa mảng(median element).
Tầm quan trọng của phân đoạn trong thuật toán quick sort
Mấu chốt chính của thuật toán quick sort là việc phân đoạn dãy số (Xem hàm partition()). Mục tiêu của công việc này là: Cho một mảng và một phần tử x là pivot. Đặt x vào đúng vị trí của mảng đã sắp xếp. Di chuyển tất cả các phần tử của mảng mà nhỏ hơn x sang bên trái vị trí của x, và di chuyển tất cả các phần tử của mảng mà lớn hơn x sang bên phải vị trí của x.
Khi đó ta sẽ có 2 mảng con: mảng bên trai của x và mảng bên phải của x. Tiếp tục công việc với mỗi mảng con(chọn pivot, phân đoạn) cho tới khi mảng được sắp xếp.
Thuật toán phân đoạn
Đặt pivot là phần tử cuối cùng của dãy số arr. Chúng ta bắt đầu từ phần tử trái nhất của dãy số có chỉ số là left, và phần tử phải nhất của dãy số có chỉ số là right -1(bỏ qua phần tử pivot). Chừng nào left < right mà arr[left] > pivot và arr[right] < pivot thì đổi chỗ hai phần tử left và right. Sau cùng, ta đổi chỗ hai phần tử left và pivot cho nhau. Xem hình minh họa phía dưới. Khi đó, phần tử left đã đứng đúng vị trí và chia dãy số làm đôi(bên trái và bên phải)
Minh họa quá trình phân đoạn trong thuật toán quick sort
Code minh họa thuật toán phân đoạn
// Code from https://nguyenvanhieu.vn
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int left = low;
int right = high - 1;
while(true){
while(left <= right && arr[left] < pivot) left++; // Tìm phần tử >= arr[pivot]
while(right >= left && arr[right] > pivot) right--; // Tìm phần tử <= arr[pivot]
if (left >= right) break; // Đã duyệt xong thì thoát vòng lặp
swap(&arr[left], &arr[right]); // Nếu chưa xong, đổi chỗ.
left++; // Vì left hiện tại đã xét, nên cần tăng
right--; // Vì right hiện tại đã xét, nên cần giảm
}
swap(&arr[left], &arr[high]);
return left; // Trả về chỉ số sẽ dùng để chia đổi mảng
}Ví dụ cho quá trình phân đoạn
arr[] = {10, 80, 30, 90, 40, 50, 70}
Indexes: 0 1 2 3 4 5 6
pivot = 6, left = 0, right = 5
arr[left] = 10 < arr[pivot] = 70 và left <= right, left = 1
arr[left] = 80 > arr[pivot] = 70, tạm dừng
arr[right] = 50 < arr[pivot] = 70, tạm dừng
Do left < right, đổi chỗ arr[left], arr[right]
arr[] = {10, 50, 30, 90, 40, 80, 70}
left = 2, right = 4
arr[left] = 30 < arr[pivot] = 70 và left <= right, left = 3
arr[left] = 90 > arr[pivot] = 70, tạm dừng
arr[right] = 40 < arr[pivot] = 70, tạm dừng
Do left < right, đổi chỗ arr[left], arr[right]
arr[] = {10, 50, 30, 40, 90, 80, 70}
left = 4, right = 3
// Do left >= right
arr[] = {10, 50, 30, 40, 70, 80, 90}. // Đổi chỗ arr[left] và arr[pivot]
Bây giờ, 70 đã nằm đúng vị trí, các phần từ <= 70 nằm phía trước và lớn hơn 70 nằm phía sau.
Quy trình của thuật toán sắp xếp quick sort
Bước 1: Lấy phần tử chốt là phần tử ở cuối danh sách.
Bước 2: Chia mảng theo phần tử chốt.
Bước 3: Sử dụng sắp xếp nhanh một cách đệ qui với mảng con bên trái.
Bước 4: Sử dụng sắp xếp nhanh một cách đệ qui với mảng con bên phải.Code minh họa hàm quickSort
// Code from https://nguyenvanhieu.vn
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
/* pi là chỉ số nơi phần tử này đã đứng đúng vị trí
và là phần tử chia mảng làm 2 mảng con trái & phải */
int pi = partition(arr, low, high);
// Gọi đệ quy sắp xếp 2 mảng con trái và phải
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}Minh họa thuật toán sắp xếp quick sort sử dụng ngôn ngữ C++
// Code from https://nguyenvanhieu.vn
#include<stdio.h>
void swap(int &a, int &b)
{
int t = a;
a = b;
b = t;
}
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int left = low;
int right = high - 1;
while(true){
while(left <= right && arr[left] < pivot) left++;
while(right >= left && arr[right] > pivot) right--;
if (left >= right) break;
swap(arr[left], arr[right]);
left++;
right--;
}
swap(arr[left], arr[high]);
return left;
}
/* Hàm thực hiện giải thuật quick sort */
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
/* pi là chỉ số nơi phần tử này đã đứng đúng vị trí
và là phần tử chia mảng làm 2 mảng con trái & phải */
int pi = partition(arr, low, high);
// Gọi đệ quy sắp xếp 2 mảng con trái và phải
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
/* Hàm xuất mảng */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main()
{
int arr[] = {10, 80, 30, 90, 40, 50, 70};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n-1);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}Kết quả chạy thử:
Sorted array:
10 30 40 50 70 80 90Đánh giá thuật toán sắp xếp quick sort
Độ phức tạp thuật toán của quick sort
- Trường hợp tốt: O(nlog(n))
- Trung bình: O(nlog(n))
- Trường hợp xấu: O(n^2)
Không gian bộ nhớ sử dụng: O(log(n))