Quick Sort là gì? Tìm hiểu chi tiết về Quick Sort

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é!

Quick Sort là gì?

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ớ.

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<stdio.h>

#include<iostream>

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 <= 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;

}

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 << 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";

}

Kết quả ta được:

Tại sao Quick Sort lại hiệu quả hơn Merge Sort?

Về không gian phụ trợ: Quick Sort là một thuật toán sắp xếp tại chỗ trong khi Merge Sort phải sử dụng thêm không gian. Sắp xếp tại chỗ có nghĩa là không có dung lượng lưu trữ bổ sung nào được sử dụng để thực hiện sắp xếp (ngoại trừ ngăn xếp đệ quy). Merge Sort yêu cầu một mảng tạm thời để hợp nhất các mảng đã sắp xếp, vì vậy Quick Sort trở thành tùy chọn tốt hơn.

Trường hợp xấu nhất: Trường hợp xấu nhất của Quick Sort là O (n2) có thể tránh được bằng cách sử dụng Quick Sort ngẫu nhiên. Lúc này sẽ có được trường hợp trung bình bằng cách chọn phần tử xoay ngẫu nhiên và cải thiện hiệu suất như Merge Sort

Thân thiện với bộ nhớ cache: Quick Sort cũng là một thuật toán sắp xếp thân thiện với bộ nhớ cache vì thuật toán này có vị trí tham chiếu tốt khi được sử dụng cho các mảng.

Tóm lại, Quick Sort là một thuật toán sắp xếp rất hữu ích trong nhiều trường hợp và được sử dụng phổ biến hiện nay. Bài viết trên đã cung cấp cho bạn một số thông tin liên quan đến Quick Sort, hy vọng bạn sẽ áp dụng thuật toán này hiệu quả để sắp xếp dữ liệu nhé!

FAQs về Quick Sort