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 như thế nào?
Quick Sort là một thuật toán sắp xếp linh hoạt, giúp người dùng tiếp cận và sắp xếp dữ liệu một cách nhanh chóng và dễ dàng.
Ứng dụng trong máy tính thương mại
Quick Sort thường được sử dụng để phân loại và sắp xếp dữ liệu nhanh chóng trong tổ chức tư nhân và cơ quan chính phủ. Ví dụ, nó có thể được áp dụng để sắp xếp các hồ sơ hoặc tài khoản theo ID hoặc tên gọi, tối ưu hóa quá trình quản lý và truy xuất thông tin.
Ứng dụng trong tính toán số
Quick Sort được sử dụng để quản lý hàng đợi ưu tiên và sắp xếp Inturn, giúp tăng độ chính xác và hiệu suất trong các phép tính số phức tạp.
Ứng dụng trong tìm kiếm thông tin
Thuật toán Quick Sort cung cấp phương pháp tìm kiếm nhanh chóng và hiệu quả cho việc truy xuất thông tin trong các hệ thống hoặc ứng dụng đòi hỏi tính linh hoạt và tốc độ trong tìm kiếm.
Độ phức tạp, hiệu quả của thuật toán QuickSort
Khi lựa chọn một thuật toán QuickSort, hiệu suất được coi là vô cùng quan trọng. Dưới đây là một số đặc điểm nổi bật về hiệu suất của thuật toán Quicksort:
- Độ phức tạp về thời gian: QuickSort có thể thực hiện với độ phức tạp từ O(n) đến O(n log n) và trong trường hợp tồi nhất là O(n^2). Điều này làm cho QuickSort trở thành một trong những thuật toán sắp xếp nhanh và hiệu quả nhất trong việc xử lý dữ liệu lớn.
- Độ phức tạp về không gian: Đối với không gian lưu trữ, độ phức tạp trung bình của QuickSort là O(log n) và trong trường hợp xấu nhất là O(n). Tuy nhiên, vấn đề với thuật toán đệ quy là không tối ưu hóa được việc sử dụng bộ nhớ, có thể dẫn đến sự lãng phí tài nguyên.
- Tối ưu hóa: Để giảm thiểu việc sử dụng không gian lưu trữ và tối ưu hóa thuật toán, QuickSort thực hiện đệ quy trên các phân vùng nhỏ hơn và sử dụng đệ quy đuôi. Ngoài ra, bạn cũng có thể kết hợp QuickSort với thuật toán sắp xếp lặp để tối ưu hóa hiệu suất đối với các mảng nhỏ.
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";
}
FAQS ( Câu Hỏi Thường Gặp)
QuickSort có tính ổn định không?
QuickSort thường không có tính ổn định. Điều này có nghĩa là trong quá trình sắp xếp, vị trí tương đối của các phần tử bằng nhau có thể thay đổi. Tuy nhiên, đôi khi có thể điều chỉnh QuickSort để làm cho nó ổn định, nhưng phương pháp này thường yêu cầu thêm chi phí tính toán và không phải là phiên bản tiêu chuẩn của thuật toán.
QuickSort có tính In-place không?
Có, QuickSort được coi là thuật toán in-place. Điều này có nghĩa là nó thực hiện sắp xếp trực tiếp trên mảng ban đầu mà không cần bất kỳ không gian bộ nhớ phụ trợ nào lớn hơn mảng ban đầu. QuickSort chỉ sử dụng một lượng hữu hạn bộ nhớ bổ sung để lưu trữ các chỉ số của mảng và không yêu cầu không gian lưu trữ bổ sung đáng kể cho việc thực hiện sắp xếp.
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. Điều này 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.
