QuickSort là gì? QuickSort hoạt động như thế nào?
QuickSort là một thuật toán sắp xếp mạnh mẽ trong khoa học máy tính, hoạt động theo cơ chế “chia để trị”.
Dưới đây là cách thuật toán QuickSort hoạt động:
- Chọn Pivot: Bước đầu tiên là chọn một phần tử làm Pivot từ mảng. Pivot thường được chọn từ đầu, cuối, hoặc ngẫu nhiên trong mảng.
- Phân chia mảng: Mảng được phân chia thành hai phần, một phần chứa các phần tử nhỏ hơn hoặc bằng Pivot và phần còn lại chứa các phần tử lớn hơn Pivot. Các phần tử bằng Pivot có thể nằm ở bất kỳ vị trí nào.
- Đệ quy: QuickSort được áp dụng đệ quy trên cả hai phần của mảng. Quá trình phân chia và sắp xếp sẽ tiếp tục cho đến khi mỗi phần tử chỉ còn đơn lẻ hoặc không thể phân chia thành các phần tử nhỏ hơn và lớn hơn.
- Kết thúc đệ quy: Khi mỗi phần tử đã được sắp xếp hoàn chỉnh, thuật toán kết thúc đệ quy và mảng được sắp xếp hoàn chỉnh.
Qua quá trình này, QuickSort có khả năng sắp xếp hiệu quả các tập dữ liệu lớn. Tuy nhiên, việc chọn Pivot đóng vai trò quan trọng, và một sự lựa chọn không tốt có thể dẫn đến hiệu suất kém của thuật toán.
Quick Sort được ứng dụng rộng rãi trong các lĩnh vực như máy tính thương mại, tính toán số, và tìm kiếm thông tin.Trong máy tính thương mại, nó được sử dụng để sắp xếp dữ liệu như hồ sơ và tài khoản. Trong tính toán số, nó giúp quản lý hàng đợi ưu tiên và sắp xếp Inturn. Trong tìm kiếm thông tin, Quick Sort giúp giúp tìm kiếm nhanh chóng và hiệu quả cho các hệ thống và ứng dụng đòi hỏi tính linh hoạt và tốc độ.
Tại sao QuickSort được ưa chuộng hơn MergeSort trong việc sắp xếp mảng?
Dưới đây chính là những lý do khiến QuickSort được ưa chuộng hơn hẳn MergeSort về QuickSort:
Về thuật toán sắp xếp mảng
- Thuật toán sắp xếp tại chỗ, không đòi hỏi thêm không gian lưu trữ, ngược lại, MergeSort yêu cầu O(N) bộ nhớ bổ sung, với N là kích thước mảng, có thể là một con số lớn.
- Không gian dư thừa được sử dụng trong quá trình phân bổ và giải phóng trong MergeSort gây ra tăng thời gian chạy của thuật toán.
Về độ phức tạp
- Cả hai thuật toán đều có độ phức tạp trung bình O(NlogN), tuy nhiên lại có các hằng số khác nhau. Sắp xếp mảng tại MergeSort mất điểm vì việc sử dụng không gian lưu trữ bổ sung O(N).
- Trong thực tế, hầu hết các triển khai của QuickSort sử dụng phiên bản ngẫu nhiên, với độ phức tạp thời gian trung bình dự kiến là O(nLogn). Mặc dù trường hợp xấu nhất có thể xảy ra trong phiên bản ngẫu nhiên, nhưng trường hợp xấu nhất không thường xảy ra với một mảng cụ thể và QuickSort ngẫu nhiên hoạt động tốt trong thực tế
Quick Sort trong lập trình C++ được diễn ra như thế nào?
Trong phần này, chúng ta thực hiện hai giai đoạn. Giai đoạn đầu tiên được gọi là phân đoạn mảng (partition()), trong khi giai đoạn thứ hai là sắp xếp (quickSort()).
- Để chọn pivot cho mảng, ta có thể lựa chọn số cuối cùng trong mảng làm pivot.
- Tạo hai biến left và right để chỉ định vị trí bên trái và bên phải của danh sách.
- Thực hiện so sánh các phần tử với pivot. Nếu phần tử nhỏ hơn pivot, di chuyển nó sang bên trái và ngược lại.
- Sau khi di chuyển, thực hiện việc sắp xếp các phần tử trong mảng con mới trước khi tiếp tục phân đoạn tiếp theo.
Để chi tiết hơn cụ thể trong từng dòng code trong thuật toán chúng tôi đã chú thích chi tiết bạn có thể tham khảo nhé!
Hàm partition()
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // : khai báo phần tử đánh dấu pivot
int left = low; // khai báo biến bên trái
int right = high - 1; // khai báo biến bên phải
while(true){
while(left <= right && arr[left] < pivot) left++; // tìm phần tử => phần tử pivot trong mảng
while(right >= left && arr[right] > pivot) right–; // tìm phần tử <= phần tử pivot trong mảng
if (left >= right) break; // sau khi duyệt xong thì thoát khỏi vòng lặp
swap(arr[left], arr[right]); // nếu chưa xong thì sử dụng hàm swap() để tráo đổi.
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
}
Hàm quicksort()
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
/* index là chỉ số nơi phần tử này đã đứng đúng vị trí
và đây là phần tử chia mảng làm 2 mảng con trái & phải */
int index = partition(arr, low, high);
// Gọi đệ quy sắp xếp 2 mảng con trái và phải
quickSort(arr, low, index - 1);
quickSort(arr, index + 1, high);
}
}
Hàm swap()
void swap(int &a, int &b)
{
int t = a;
a = b;
b = t;
}
Minh họa sắp xếp Quick Sort trong mảng
Để minh họa, ta sẽ thực hiện một ví dụ với việc áp dụng thuật toán sắp xếp nhanh (Quick Sort). Dưới đây là một mảng cụ thể: arr[] = {9, -3, 5, 2, 6, 8, -6, 1, 3} và được sắp xếp theo thứ tự tăng dần.
Code mẫu:
#include<stdio.h>
#include<iostream>
using namespace std;
//tạo hàm swap để tráo đổi các vị trí
void swap(int &a, int &b)
{
int t = a;
a = b;
b = t;
}
// phân đoạn trong mảng
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // khai báo phần tử đánh dấu pivot
int left = low; //khai báo biến bên trái
int right = high - 1; //khai báo biến bên phải
while(true){
while(left <= right && arr[left] < pivot) left++; // tìm phần tử >= phần tử pivot trong mảng
while(right >= left && arr[right] > pivot) right--; // tìm phần tử <= phần tử pivot trong mảng
if (left >= right) break; // sau khi duyệt xong thì thoát khỏi vòng lặp
swap(arr[left], arr[right]); // nếu chưa xong thì sử dụng hàm swap() để tráo đổi.
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
}
/* Hàm thực hiện giải thuật quick sort */
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
// index là chỉ số nơi phần tử này đã đứng đúng vị trí và đây là phần tử chia mảng làm 2 mảng con trái & phải
int index = partition(arr, low, high);
// Gọi đệ quy sắp xếp 2 mảng con trái và phải
quickSort(arr, low, index - 1);
quickSort(arr, index + 1, high);
}
}
/* Hàm xuất mảng */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++){
cout << arr[i];
cout<<"\t";
}
}
int main()
{
int arr[] = {9, -3, 5, 2, 6, 8, -6, 1, 3};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n-1);
cout<<"Mảng sau khi được sắp xếp: \n";
printArray(arr, n);
cout<<"\n---------------------------------------\n";
cout<<"Chương trình này được đăng tại Freetuts.net";
}
QuickSort 3 chiều là gì?
QuickSort 3 chiều là một biến thể của thuật toán QuickSort cổ điển. Khi sử dụng QuickSort 3 chiều, mảng được chia thành ba phần thay vì hai phần như trong QuickSort thông thường. Cụ thể, các phần tử trong mảng được phân chia thành ba phần sau quá trình sắp xếp:
- Các phần tử nhỏ hơn hoặc bằng pivot.
- Các phần tử bằng pivot.
- Các phần tử lớn hơn pivot.
Quá trình này giúp giảm số lần di chuyển các phần tử và tăng hiệu suất sắp xếp trong trường hợp mảng chứa nhiều phần tử trùng lặp giúp giảm đáng kể thời gian thực hiện trong trường hợp mảng có nhiều phần tử trùng lặp, giúp tối ưu hiệu suất của thuật toán QuickSort.
Lời kết
Dưới đây là một số thông tin về thuật toán khái niệm Quick Sort là gì cũng như hoạt động trong việc sắp xếp mảng. Mong rằng những kiến thức trên sẽ cung cấp cho bạn những hiểu biết cần thiết để phục vụ cho quá trình học tập và làm việc, đặc biệt là đối với những ai đam mê lĩnh vực lập trình.
