Các thuật toán sắp xếp dữ liệu là một yếu tố quan trọng khá quan trọng trong lập trình, điển hình trong số đó là Quick Sort. Vậy Quick Sort là gì? Trong bài viết hôm nay, bạn hãy cùng Tino Group tìm hiểu về Quick Sort để xem cách thuật toán này triển khai và hoạt động như thế nào nhé!
Khái niệm Quick Sort
Thuật toán Quick Sort [Sắp xếp nhanh] là một quy trình có hệ thống để sắp xếp các phần tử của một mảng. Giống như Merge Sort, QuickSort là một thuật toán sử dụng cách thức chia để trị [Divide and Conquer algorithm].
Tên gọi “Quick Sort” ám chỉ thuật toán này có khả năng sắp xếp dữ liệu nhanh hơn nhiều so với bất kỳ thuật toán sắp xếp truyền thống nào khác. Tuy nhiên, Quick Sort không được ổn định vì thứ tự tương đối của các phần tử bằng nhau không được đảm bảo.
Cách thức hoạt động của Quick Sort
Thuật toán sẽ chọn ra một phần tử trong mảng để làm điểm đánh dấu gọi là pivot. Sau khi chọn được điểm đánh dấu, nó sẽ chia mảng đó thành hai mảng con bằng cách so sánh với pivot đã chọn. Một mảng sẽ bao gồm các phần tử nhỏ hơn hoặc bằng pivot và mảng còn lại luôn lớn hơn hoặc bằng pivot.
Sau đó, quá trình này được lặp lại đủ số lần cho đến khi các mảng nhỏ có thể được sắp xếp một cách dễ dàng để tạo ra một tập dữ liệu được sắp xếp đầy đủ.
Các nhiều phiên bản Quick Sort khác nhau chọn pivot theo những cách khác nhau. Tốc độ sắp xếp của thuật toán phải phụ thuộc vào việc lựa chọn pivot, có một số cách để chọn như sau:
- Luôn chọn phần tử đầu tiên làm pivot.
- Luôn chọn phần tử cuối cùng làm pivot
- Chọn một phần tử ngẫu nhiên làm pivot.
- Chọn vị trí ở giữa làm pivot.
Ứng dụng của thuật toán Quick Sort
Quick Sort cung cấp một cách tiếp cận nhanh chóng và có phương pháp để sắp xếp bất kỳ thứ gì. Sau đây là một số ứng dụng của Quick Sort
- Máy tính thương mại: Được sử dụng trong các tổ chức chính phủ và tư nhân với mục đích phân loại dữ liệu khác nhau như sắp xếp tài khoản/hồ sơ theo tên hoặc theo ID, phân loại giao dịch theo thời gian hoặc địa điểm, phân loại file theo tên hoặc ngày tạo, v.v.
- Tính toán số: Hầu hết các thuật toán được phát triển hiệu quả sử dụng hàng đợi ưu tiên và sắp xếp inturn để đạt được độ chính xác trong tất cả các phép tính.
- Tìm kiếm thông tin: Thuật toán sắp xếp hỗ trợ tìm kiếm thông tin nhanh hơn và hiệu quả hơn
Độ phức tạp của Quick Short
Khi chọn một thuật toán sắp xếp, hiệu quả là một trong những yếu tố quan trọng nhất. Dưới đây là một số điểm hiệu quả của thuật toán Quicksort.
Độ phức tạp về thời gian của Quick Short
Trong các trường hợp tốt nhất, trung bình và xấu nhất, thuật toán Quick Sort thực hiện với độ phức tạp O [n], O [n log n] và O [n ^ 2] tương ứng. Đây là một trong những thuật toán sắp xếp hiệu quả nhất khi nói đến độ phức tạp về thời gian.
Độ phức tạp về không gian của Quick Short
Độ phức tạp không gian trung bình của Quick Sort là O [log n] và độ phức tạp không gian trong trường hợp xấu nhất là O [n]. Điều này ngang bằng với hầu hết các thuật toán sắp xếp phổ biến, nhưng bản chất của thuật toán đệ quy là chúng không tối ưu hóa việc sử dụng bộ nhớ.
QUẢNG CÁO
Tối ưu hóa
Với bất kỳ thuật toán nào, thường có một số tối ưu hóa có thể được áp dụng cho các trường hợp khác. Để đảm bảo rằng không gian đã sử dụng được giới hạn ở O [log n], thuật toán có thể được thực hiện để đệ quy vào phía nhỏ hơn của phân vùng và cũng sử dụng đệ quy đuôi. Người ta cũng có thể triển khai một thuật toán sắp xếp kết hợp chuyển sang một thuật toán sắp xếp lặp đi lặp lại có thể hiệu quả hơn về thời gian cho các mảng nhỏ hơn.
Thuật toán Quick Sort trong ngôn ngữ lập trình C++
Mô tả thuật toán
Thuật toán sẽ có hai giai đoạn. Giai đoạn đầu là phân đoạn mảng [partition[]] và giai đoạn sau là sắp xếp [quickSort[]].
- Chọn pivot cho mảng.
- Tạo hai biến là left và right để trỏ đến bên trái và bên phải của danh sách.
- Tiến hành so sánh các phần tử với pivot. Trong trường hợp phần tử nhỏ hơn pivot thì dịch chuyển qua bên trái và ngược lại.
- Sau khi đã dịch chuyển thì tiến hành công 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.
Code thuật toán Quick Sort trong C++
Ở phần trên đã trình bài các bước viết thuật toán. Để chi tiết hơn, bạn hãy tham khảo các dòng code trong thuật toán dưới đây.
Hàm partition[]
Hàm quicksort[]
Hàm swap[]
Ví dụ về Quick Sort trong mảng
Để minh họa cho hình ảnh ở trên, chúng ta hãy cùng làm một ví dụ áp dụng thuật toán sắp xếp nhanh [Quick Sort]. Sắp xếp các phần tử trong mảng arr[] = {9, -3, 5, 2, 6, 8, -6, 1, 3} theo thứ tự tăng dần.
# include
# include
using namespace std;
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];
int left = low;
int right = high - 1;
while[true]{
while[left = left && arr[right] > pivot] right--;
if [left >= right] break;
swap[arr[left], arr[right]];
left++;
right--;
}
swap[arr[left], arr[high]];
return left;
}
void quickSort[int arr[], int low, int high]
{
if [low < high]
{
int index = partition[arr, low, high];
quickSort[arr, low, index - 1];
quickSort[arr, index + 1, high];
}
}
void printArray[int arr[], int size]
{
int i;
for [i=0; i < size; i++]{
cout