Sắp xếp-- quicksort and merge sort

Trong bài này chúng ta sẽ áp dụng phương pháp chia để trị (divide and conquer) trong bài toán sắp xếp. Hai phương pháp sắp xếp đặc trưng dựa trên chia để trị là Quick SortMerege Sort.

Problem: Cho một mảng gồm $n$ phần tử $A[1,2,\ldots,n]$, sắp xếp các phần tử của mảng theo thứ tự tăng dần.

 
Quick Sort
 
Quick Sort được phát minh bởi Tony Hoare 1959. Quick Sort là một thuật toán sắp xếp khá nhanh trong thực tế mặc dù trong trường hợp tồi nhất là $O(n^2)$. Phiên bản randomized của Quicksort có thời gian kì vọng (expected) là $O(n\log n)$, với hằng số đằng sau $O$ khá nhỏ. Điều đó giải thich một phần vì sao Quick Sort cũng hay được dùng trong thực tế. Ta sẽ tìm hiểu thêm trong bài thuật toán ngẫu nhiên.

Tư tưởng của quick sort khá đơn giản và gồm hai bước chính:

  1. Bước 1: chọn một phần tử của mảng (bất kì), $A[p]$, gọi là pivot, và phân mảng thành hai phần: phần 1 gồm những phần tử nhỏ hơn hoặc bằng $A[p]$ và phần 2 gồm những phần tử lớn hơn $A[p]$.
  2. Bước 2: gọi đệ quy sắp xếp phần 1 và phần 2

Dưới đây là giả mã của thuật toán. Hàm Partition($A[1,2,\ldots, n],p$) chia mảng $A$ thành hai phần với pivot được chọn là $A[p]$, và trả lại vị trí mới của $A[p]$ trong mảng sau khi đã chia.

QuickSort($A[1,2,\ldots, n]$):
    if$(n > 1)$
        Choose a pivot element $A[p]$
       $r \leftarrow $ Partition($A[1,2,\ldots, n],p$)
        QuickSort($A[1,2,\ldots, r-1]$)
        QuickSort($A[r+1,2,\ldots, n]$)

 
Dưới đây là code C của giả mã trên:

// x, y is the first and last index of array _array
void quick_sort(int _array[], int x, int y){
if(x < y) {
int p = (y+x)/2;// choose pivot to be the middle element
int r = partition(_array, x,y,p);
quick_sort(_array, x,r-1);
quick_sort(_array, r+1,y);
}
}
}

Giả mã của thuật toán chia mảng với phân tử chọn (pivot) là $A[p]$, trả lại vị trí mới cuả phần tử có giá trị $A[p]$ trong mảng.

Partition($A[1,2,\ldots, n],p$):
    swap $A[p] \leftrightarrow A[n]$
    $i \leftarrow 0$
    $j \leftarrow n$
    while $i$ < $j$
       repeat $i \leftarrow i + 1$ until $(i \geq j \mbox{ or } A[i]\geq A[n])$
       repeat $j \leftarrow j - 1$ until $(j \geq i \mbox{ or } A[j]< A[n])$
       if $i$ < $j$
          swap $A[i] \leftrightarrow A[j]$
    swap $A[i] \leftrightarrow A[n]$
    return $i$

 
Dưới đây là code C của giả mã trên. Có đôi chút khác biệt khi ta thực thi bằng C vì mảng bắt đầu từ phần tử 0 và mình dùng while (do đã quen) thay vì do while để thực hiện giả mã repeat.

// x, y is the first and last index of array arr
// p is the index of the pivot, x &amp;amp;amp;lt;= p &amp;amp;amp;lt;= y
int partition(int arr[], int x, int y, int p){
swap(&amp;amp;amp;amp;arr[p],&amp;amp;amp;amp;arr[y]);
int i = x;
int j = y-1;
while( i &amp;amp;amp;lt;= j){
while(arr[i] &amp;amp;amp;lt; arr[y] &amp;amp;amp;amp;&amp;amp;amp;amp; i &amp;amp;amp;lt;= j){i++;}
while(arr[j] &amp;amp;amp;gt;= arr[y] &amp;amp;amp;amp;&amp;amp;amp;amp; i &amp;amp;amp;lt;= j){j--;}
if(i &amp;amp;amp;lt; j) swap(&amp;amp;amp;amp;arr[i],&amp;amp;amp;amp;arr[j]);
}
swap(&amp;amp;amp;amp;arr[i],&amp;amp;amp;amp;arr[y]);
return i;
}

Code đầy đủ bằng C sẽ được cho ở cuối bài.

Phân tích thời gian
Nhìn vào giả mã cho thuật toán thực hiện Partition($A[1,2,\ldots, n],p$): dễ thấy thời gian thực hiện là $O(n)$. Như vậy, thời gian tính của Quick Sort là:

$T(n) = T(r-1) + T(n-r) + O(n)$

 
Ở đây $r$ phụ thuộc vào việc chọn phần tử pivot $A[p]$. Trong trường hợp tồi nhất, trong mỗi lần đệ quy, phần tử pivot chi mảng thành một phần có 1 phần tử và phần còn lại có n-2 phần tử. Như vậy thời gian là $T(n) = T(n-2) + O(n) \Rightarrow T(n) = O(n^2)$ (xem tại đây để biết tại sao). Như vậy các bạn có thể ghi nhớ, trong trường hợp tồi nhất, Quick Sort có thời gian chạy là $O(n^2)$.

Trong trường hợp lí tưởng, phần tử pivot chọn luôn chia mảng thành hai phần xấp xỉ như nhau. Như vậy ta có $T(n) = 2 T(n/2) + O(n) \Rightarrow T(n) = O(n\log n)$. Như đã nói đến trong bài median selectionn, trong những trường hợp không biết chọn phần tử nào là pivot tốt, cách đầu tiên có thể nghĩ tời là chọn ngẫu nhiên một phần tử của mảng làm pivot, với xác suất như nhau. Với Quick Sort, chọn ngẫu nhiên sẽ cho ta thuật toán với thời gian kì vọng (expected) là $O(n\log n)$. Chi tiết sẽ thảo luận trong phần thuật toán ngẫu nhiên.

Cách khác là có thể áp dụng thuật toán median selection với thời gian tuyến tính để chọn pivot. Về mặt lí thuyết, thời gian tính là $O(n\log n)$ như hằng số trong biều thức $O$ sẽ khá cao. Nếu thực thi thực tế sử dụng cách này sẽ rất chậm.

Merge Sort

Merge Sort được phát minh bởi John von Neumann vào năm 1945 là một thuật toán sắp xếp luôn đảm bảo thời gian chạy tồi nhất là $O(n\log n)$ dựa trên kĩ thuật chia để trị. Ý tưởng cơ bản của Merge Sort gồm hai bước:

  1. Bước 1: chia mảng thành hai phần với kích thước (xấp xỉ) bằng nhau, sau đó gọi đệ quy sắp xếp trên mỗi phần. Chú ý ở đây khác với Quick Sort, ta không dùng pivot.
  2. Bước 2: trộn (merge) hai phần đã sắp xếp ở bước 1 thành một mảng.

Dưới đây là giả mã của thuật toán. Hàm Merge($A[1,2,\ldots, n],m$) trộn hai mảng con $A[1,2,\ldots, m]$, $A[m+1,m+2, \ldots, n]$ đã sắp xếp thành mảng $A[1,2,\ldots,n]$ đã xắp xếp.

MergeSort($A[1,2,\ldots, n]$):
    if$(n > 1)$
        $m \leftarrow \lfloor n/2\rfloor$
        MergeSort($A[1,2,\ldots, m]$)
        MergeSort($A[m+1,2,\ldots, n]$)
        Merge($A[1,2,\ldots, n],m$)

 
Code của giả mã bằng C:

// x, y is the first and last index of array _array
void merge_sort(int _array[], int x, int y){
if(x &amp;amp;amp;amp;lt; y){
int m = (y + x +1)/2-1;
merge_sort(_array, x, m);
merge_sort(_array, m+1,y);
merge(_array, x, y, m);
}
}

Giả mã của hàm Merge($A[1,2,\ldots, n],m$)

Merge($A[1,2,\ldots, n]$):
    $i \leftarrow 1; j \leftarrow m+1$
    for $k \leftarrow 1$ to $n$
        if $j > n$
           $B[k] \leftarrow A[i]; i \leftarrow i + 1$
        else if $i > m$
           $B[k] \leftarrow A[j]; j \leftarrow j + 1$
        else if $A[i] < A[j] $
           $B[k] \leftarrow A[i]; i \leftarrow i + 1$
        else
           $B[k] \leftarrow A[j]; j \leftarrow j + 1$
    for $k \leftarrow 1$ to $n$
       $A[k] \leftarrow B[k]$

 
Code của giả mã bằng C:

// x, y is the first and last index of array _array
void merge(int _array[], int x, int y, int pivot){
int i = x, k = 0;
int j = pivot + 1;
int size = y-x+1;
int _brray[y-x+1];
memset(_brray, 0, sizeof(_brray));
for(k = 0 ; k &amp;amp;amp;amp;lt; size; k ++) {
if(j &amp;amp;amp;amp;gt; y) {
_brray[k] = _array[i]; i ++;
} else if(i &amp;amp;amp;amp;gt; pivot) {
_brray[k] = _array[j]; j ++;
} else if(_array[i] &amp;amp;amp;amp;lt; _array[j]){
_brray[k] = _array[i]; i++;
} else {
_brray[k] = _array[j]; j++;
}
}
for(i = 0; i &amp;amp;amp;amp;lt; size ; i++) _array[x+i] = _brray[i];
}

Phân tích thời gian
Nhìn vào giả mã ta có thể thấy hàm Merge có thể thực hiện trong thời gian tuyến tính $O(n)$. Như vậy thời gian thực hiện của Merge Sort là

$T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + O(n)$

 
Để đơn giản, ta có thể bỏ dấu phần nguyên trên và dưới. Như vậy thời gian thực hiện của Merge Sort là $T(n) = 2T(n/2) + O(n) \Rightarrow T(n) = O(n\log n)$.

Code: merge sort and quick sort

Tham khảo

Bài viết dự chủ yêu trên notes của Jeff Erickson
http://web.engr.illinois.edu/~jeffe/teaching/algorithms/notes/01-recursion.pdf

Tài liệu tham khảo liên quan:
[1] Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001) [1990]. Introduction to Algorithms (2nd ed.) . MIT Press and McGraw-Hill. ISBN 0-262-03293-7
Facebook Comments

Tags: , , ,

  1. hoahuongduong’s avatar

    Mình có một nhận xét thế này đúng ko ạ: giả sử đầu vào là dãy có n số bằng nhau hết, n rất lớn, lúc đấy thời gian sắp xếp của Q - sort luôn là O(n^2) cho dù có sử dụng thuật chọn trung vị đi nữa.

    Reply

    1. Hùng Lê’s avatar

      Nhận xét của bạn hoàn toàn đúng. Có nhiều cách để giải quyết trường hợp này. Ví dụ khi bạn so sánh pivot với một phần tử bằng nó, bạn sử dụng một counter để đếm xem bao nhiêu phần tử bằng với pivot mà ta đã so sánh, rồi quyết định đưa phần tử này sang trái hay sang phải. Cách này không làm tăng thời gian tiệm cận của Quicksort. Thông thường, để phân tích đơn giản, ta sẽ giả sử các phần tử luôn khác nhau.

      Reply

Reply

Your email address will not be published. Required fields are marked *