Quick Sort là gì? Tìm hiểu thuật toán sắp xếp nhanh Quick Sort

Quick Sort là một thuật toán cơ bản mà mọi lập trình viên đều phải biết đến. Mặc dù là thứ mà ai cũng biết, nhưng để thành thạo thật sự chưa chắc đã dễ dàng như nhiều người tưởng tượng. Hãy cùng chúng tôi đi tìm hiểu về những kiến thức xung quanh cũng như đi sâu một chút về ý nghĩa của thuật toán này nhé! Bạn sẽ không muốn bỏ lỡ những thông tin trong bài viết này đâu.

Khái niệm về thuật toán Quick Sort ?

Quick sort là một thuật toán sắp xếp hay còn được gọi là sắp xếp kiểu phân chia (Part Sort), được phát triển từ những năm 1960 và vẫn thông dụng cho đến những ngày hôm nay. Thuật toán hoạt động giống như thuật toán Merge Sort là chia để trị (Divide and Conquer algorithm) bằng cách chọn ra rồi một phần tử chốt (pivot) làm điểm đánh dấu rồi so sánh từng phần tử trong danh sách với nó, đồng thời chia danh sách ra làm các mảng nhỏ hơn nhờ phân chia các phần tử lớn hơn hay nhỏ hơn hoặc bằng với phần tử chốt ban đầu và sắp xếp lại một cách nhanh chóng. 

Đánh giá về thuật toán 

• Phân loại: Giải thuật sắp xếp
• Mức độ phức tạp: Trung bình O*(n*log n)
• Thời gian xấu nhất: O*(n^2)
• Không gian bộ nhớ được sử dụng: O(log(n))
• Tần suất tối ưu: Thỉnh thoảng

Thuật toán sắp xếp trong thường được sử dụng để xử lý các tệp dữ liệu không lớn. Bộ dữ liệu này sẽ được toàn bộ đưa vào trong bộ nhớ của máy tính. Còn những thuật toán sắp xếp ngoài chỉ được dành riêng cho các tệp lớn mà dữ liệu không thể mang toàn bộ dữ liệu vào tới bộ nhớ trong cùng một lúc nhưng có thể lần lượt từng phần ở bộ nhớ ngoài.

Cách chọn phần tử chốt

Mức độ phức tạp của bài toán được quyết định phần lớn dựa vào kỹ thuật chọn phần tử chốt (pivot) của người dùng. Bài toán sẽ đạt được điều kiện tốt nhất khi mà chọn phần tử nằm có giá trị nằm ở khoảng giữa của danh sách làm phần tử chốt. Bằng cách này chúng ta chỉ cần thực hiện log2(n) lần chia để đạt được kích thước mảng con bằng 1. Khi đó ta sẽ được một mảng đã sắp xếp một cách hoàn chỉnh.

Dưới đây là một vài cách để chọn phần tử chốt:

• Luôn chọn phần tử đứng đầu hoặc đứng cuối làm phần tử chốt.
• Chọn phần tử ở vị trí giữa danh sách làm phần tử chốt.
• Chọn phần tử có giá trị nằm giữa mảng trong ba phần tử đứng đầu, đứng giữa hoặc đứng cuối làm phần tử chốt.
• Chọn một phần tử ngẫu nhiên làm phần tử chốt. Lưu ý: Sử dụng cách này có những rủi ro đi kèm như vòng lặp vô tận hoặc những trường hợp đặc biệt khác.

Ý tưởng thực hiện thuật toán Quick Sort

Bước 1: Chọn phần tử chốt.

Bước 2: Khai báo hai biến con trỏ để có thể duyệt từ hai phía của phần tử chốt.

Bước 3: Biến bên trái trỏ đến từng phần tử của mảng con bên trái của phần tử chốt.

Bước 4: Biến bên phải trỏ đến từng phần tử của mảng con bên phải của phần tử chốt.

Bước 5: Đến khi biến bên trái nhỏ hơn phần tử chốt thì di chuyển sang phải.

Bước 6: Đến khi biến bên phải nhỏ hơn phần tử chốt thì di chuyển sang trái.

Bước 7: Nếu không xảy ra trường hợp ở bước 5 và 6 thì tráo giá trị của biến bên trái và bên phải cho nhau.

Bước 8: Nếu bên trái lớn hơn bên phải thì chọn làm giá trị chốt mới.

Tìm hiểu thêm thông tin:

• Giải mà về thuật toán Dijkstra tìm đường đi ngắn nhất
• Quy hoạch động là gì? Tìm hiểu về thuật toán quy hoạch động

Tính độ phức tạp của thuật toán Quick Sort

Công thức tính toán thời gian xử lý của thuật toán Quick Sort được trình bày như sau:

T(n) = T(k) + T(n-k-1) + θ(n)

Trong công thức trên:

T(k) và T(n-k-1) là thời gian dành cho hai cuộc gọi đệ quy. 

θ(n) gọi là tiến trình phân vùng. 

k chính là số phần tử nhỏ hơn phần tử chốt.

Thời gian giải quyết thuật toán phụ thuộc nhiều vào mảng đầu tiên và cách chọn phần tử chốt.

• Nếu phân đoạn không cân bằng: Xảy ra trường hợp xấu nhất (phần tử chốt là phần tử đầu và dãy đã được sắp xếp nhanh), độ phức tạp của thuật toán Quick Sort sẽ là O(n^2). Tại thời điểm đó, mảng không được chia ra, hai bài toán con lần lượt có kích thước là n-1 và 0.
• Nếu phân đoạn hoàn hảo: Mỗi bài toán con có kích thước là n/2. Mảng cũng được phân thành hai mảng có độ dài bằng nhau. Độ phức tạp của bài toán được tính là O(nlogn).
• Nếu phân đoạn cân bằng: Một bài toán con có kích thước là n-k, bài còn lại có kích thước là k. Lúc này độ phức tạp của bài toán sẽ là O(n).

Minh họa thuật toán

Code sử dụng 

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ụ minh hoạ về quá trình phân đoạn 

arr[] = {10, 80, 30, 90, 40, 50, 70}

Index:  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[pivot] với arr[left]

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.

Ví dụ về Quick Sort đệ quy sử dụng C: 

#include<stdio.h>

#include<conio.h>

typedef int keytype;

typedef struct{

keytype key;

}recordtype;

void Swap(recordtype *x, recordtype *y){

recordtype temp;

temp = *x;

*x = *y;

*y = temp;

}

int FindPivot(recordtype a[],int i, int j){

keytype firstkey;

int k;

k=i+1;

firstkey = a[i].key;

while((k<=j)&&(a[k].key==firstkey))

k++;

if(k>j)

return -1;

else

if((a[k].key > firstkey))

return k;

else

return i;

}

int Partition(recordtype a[],int i, int j, keytype pivot){

int L, R;

L=i;

R=j;

while(L<=R){

while (a[L].key < pivot) L++;

while (a[R].key > pivot) R–;

if (L < R) Swap(&a[L], &a[R]);

}

return L;

}

void QuickSort (recordtype a[], int i, int j){

keytype pivot;

int pivotindex, k;

pivotindex = FindPivot(a,i, j);

if (pivotindex != -1){

pivot = a[pivotindex].key;

k = Partition(a, i, j, pivot);

QuickSort(a, i, k-1);

QuickSort(a, k, j);

}

}

int main(){

int n,i;

recordtype a[50];

printf(“nhap n: “);

scanf(“%d”,&n);

for(i=0;i<n;i++){

printf(“nhap phan tu: “);

scanf(“%d”,&a[i].key);

}

QuickSort(a, 0, n-1);

for(i= 0;i<n;i++){

printf(” — %d”,a[i].key);

}

return 0;

}

Qua bài viết vừa rồi, mong rằng các bạn đã tìm được những thông tin, kiến thức bổ ích về thuật toán Quick Sort phổ biến trong giới lập trình viên này. Để có thể học được những cách áp dụng, những bài học phù hợp hơn với bản thân mình, hãy liên hệ ngay với FPT Aptech để tìm cho mình những khoá học với đầy đủ mọi trình độ dành riêng cho bạn.