Một số thuật toán sắp xếp đơn giản (phần 2)

1. Một số thuật toán sắp xếp đơn giản (phần 1)

Chào các bạn, tiếp nối bài viết về thuật toán sắp xếp trước đó, hôm nay mình xin phép được giới thiệu thêm 2 thuật toán nữa đó là Quick Sort và Merge Sort, bên cạnh đó là những ví dụ cơ bản để giúp các bạn có cái nhìn khái quát hơn, đồng thời xác định được ưu, nhược điểm của từng thuật toán để áp dụng vào bài toán thực tế.

1. Giới thiệu

Sắp xếp nhanh (Quick Sort) còn có một tên gọi khác là sắp xếp phân chia (Part Sort) dựa trên ý tưởng thuật toán. Nó được phát minh lần đầu bởi C.A.Hoare vào năm 1960. Có lẽ đây là thuật toán được nghiên cứu và sử dụng rộng rãi nhất trong các thuật toán sắp xếp. Quick sort cũng là thuật toán đệ quy. Ngược với Mergesort gọi đệ quy rồi mới xử lý, Quick sort xử lý xong mới gọi đệ quy.

Ý tưởng của thuật toán này dựa trên phương pháp chia để trị, nghĩa là chia dãy cần sắp xếp thành 2 phần, sau đó thực hiện việc sắp xếp cho mỗi phần độc lập nhau. Để làm việc này thì ta cần phải làm các bước sau:

1. Chọn ngẫu nhiên một phần tử nào đó của dãy làm phần tử khóa (pivot) Kĩ thuật chọn phần tử khóa rất quan trọng vì nếu không may bạn có thể bị rơi vào vòng lặp vô hạn đối với các trường hợp đặc biệt. Tốt nhất là chọn phần tử ở vị trí trung tâm của dãy. Khi đó sau lần phân chia ta sẽ đạt tới kích thước danh sách bằng 1. Tuy nhiên điều đó rất khó. Có các cách chọn phần tử khóa như sau:

• Chọn phần tử đứng đầu hoặc đứng cuối làm phần tử khóa.

• Chọn phần tử đứng giữa danh sách làm phần tử khóa.

• Chọn phần tử trung gian trong 3 phần tử đứng đầu, đứng giữa và đứng cuối làm phần tử khóa.

• Chọn phần tử ngẫu nhiên làm phần tử khóa. (Cách này có thể dẫn đến khả năng rơi vào các trường hợp đặc biệt)

2. Xếp các phần tử nhỏ hơn phần tử chốt ở phía trước phần tử khóa

3. Xếp các phần tử lớn hơn phần tử chốt ở phía sau phần tử khóa Để có được sự phân loại này thì ở 2 bước trên, các phần tử sẽ được so sánh với khóa và hoán đổi vị trí cho nhau hoặc cho khóa nếu nó lớn hơn khóa mà lại nằm trước khóa, hoặc nhỏ hơn mà lại nằm sau khóa. Áp dụng kĩ thuật như trên cho mỗi đoạn đó và tiếp tục làm vậy cho đến khi mỗi đoạn chỉ còn 2 phần tử. Khi đó toàn bộ dãy đã được sắp xếp

Quick sort là một thuật toán dễ cài đặt, hiệu quả trong hầu hết các trường hợp và tiêu tốn ít tài nguyên hơn so với các thuật toán khác. Độ phức tạp trung bình của giải thuật là O(NlogN).

2. Các bước thực hiện giải thuật

Giả sử ta có một dãy các phần tử như sau:

left = 0; right = 7; Ở ví dụ này ta lấy một phần tử làm khóa, ở đây mình chọn phần tử khóa là A[(0+7)/2] = A[3] = 30 Cho i chạy từ trái sang phải, bắt đầu từ vị trí 0 Cho j chạy từ phải sang trái, bắt đầu từ vị trí 7 Quá trình duyệt từ bên trái với biến duyệt i sẽ dừng lại ở 56 (i=2), vì đây không phải là phần tử nhỏ hơn khóa. Quá trình duyệt từ bên phải với biến duyệt j sẽ dừng lại ở 18 (j=7) vì đây là phần tử nhỏ hơn khóa. Tiến hành đổi chỗ 2 phần tử cho nhau.

Quá trình duyệt tiếp tục. Khóa ở đây vẫn là 30. Ta tiếp tục tăng biến duyệt i và giảm biến duyệt j, nhận thấy biến duyệt i chạy đến 30 (i=3), còn biến duyệt j dừng lại ở 24 (j=6). Tiến hành đổi chỗ 2 phần tử cho nhau.

Quá trình duyệt tiếp tục. Khóa ở đây vẫn là 30. Tiếp tục tăng biến duyệt i và giảm biến duyệt j, nhận thấy biến duyệt i chạy đến 32 (i=5), còn biến duyệt j dừng lại ở 30(j=6). Tiến hành đổi chỗ 2 phần tử cho nhau.

Quá trình duyệt tiếp tục. Khóa ở đây vẫn là 30. Tiếp tục tăng biến duyệt i và giảm biến duyệt j, nhận thấy biến duyệt i và j cùng chạy đến 30. Lúc này ta sẽ chia mảng trên ra làm 2 mảng con A[0..4] và A[5..7], vì ta thấy A[5..7] đã được sắp xếp tăng dần rồi nên ta sẽ xét A[0..4] A[0..4] = [28, 16, 18, 24, 17] Lặp lại những bước trên với phần tử được chọn là khóa là A[(0+4)/2] = A[2] = 18 left = 0; right = 4; Cho i chạy từ trái sang phải bắt đầu từ vị trí 0 Cho j chạy từ phải sang trái bắt đầu từ vị trí 4 Quá trình duyệt từ bên trái với biến duyệt i sẽ dừng lại ở 28(i=0) vì đây không phải là phần tử nhỏ hơn khóa. Quá trình duyệt từ bên phải với biến duyệt j sẽ dừng lại ở 17 (j=4) vì đây là phần tử không lớn hơn khóa. Tiến hành đổi chỗ 2 phần tử cho nhau.

Quá trình duyệt tiếp tục. Tăng biến duyệt i và giảm biến duyệt j. Lúc này i = j nên ta sẽ chia mảng trên ra làm 2 mảng con A[0..1] và A[2..4]. Ta thấy A[2..4] đã được sắp xếp tăng dần rồi, nên ta chỉ xét A[0..1], vì A[0] > A[1] nên ta đổi chỗ 2 phần tử cho nhau và được mảng sắp xếp tăng dần cuối cùng:

3. Cài đặt giải thuật

Như đã nói ở trên, Quick sort cũng là một thuật toán đệ quy, bao gồm việc chia mảng thành 2 mảng con thỏa mãn yêu cầu trên, sau đó thực hiện lời gọi đệ quy với 2 mảng con vừa tạo được. Giả sử mảng được giới hạn bởi 2 tham số left và right cho biết chỉ số đầu và cuối của mảng, khi đó thuật toán được cài đặt như sau:

void QuickSort(int left, int right) 
{
    int x = A[(left + right)/2]; //luu gia tri phan tu giua mang
    int i = left;
    int j = right;
    
    do {
        //tim phan tu khong nho hon x theo i
        while(A[i] < x)
            i++;
        //tim phan tu khong lon hon x theo j
        while(A[j] > x)
            j--;
        //neu i nam truoc j thi thuc hien hoan vi
        if(i <= j) {
            swap(A[i], A[j]); //hoan vi 2 phan tu tai vi tri i va j
            //sau khi hoan vi thi tang i va giam j
            i++;
            j--;
        }
    } while(i < j);
    //neu left < j thi tiep tuc chia mang de sap xep
    if (left < j) 
        QuickSort(left, j);
    //neu i < right thi tiep tuc chia mang de sap xep 
    if (i < right)
        QuickSort(i, right);
}

4. Phân tích

Nhược điểm của Quick Sort là không hiệu quả trên những dãy đã được sắp xếp sẵn. Khi đó ta phải mất N lần gọi đệ quy và mỗi lần chỉ loại được 1 phần tử. Thời gian thực hiện thuật toán trong trường hợp xấu nhất này là O(n2). Trong trường hợp tốt nhất, mỗi lần phân chia sẽ được 2 nửa dãy bằng nhau, khi đó thời gian thực hiện thuật toán là: T(N) = 2T(N/2) + N Khi đó T(N) xấp xỉ bằng NlogN. Như vậy Quick sort là thuật toán hiệu quả trong đa số các trường hợp. Nhưng đối với các trường hợp việc sắp xếp chỉ phải thực hiện ít và lượng dữ liệu lớn thì nên sử dụng một số thuật toán khác ví dụ như Merge sort dưới đây.

1. Giới thiệu

Trong khoa học máy tính, sắp xếp trộn (merge sort) là một thuật toán sắp xếp để sắp xếp các danh sách (hoặc bất kỳ cấu trúc dữ liệu nào có thể truy cập tuần tự, v.d. luồng tập tin) theo một trật tự nào đó. Nó được xếp vào thể loại sắp xếp so sánh. Thuật toán này là một ví dụ tương đối điển hình của lối thuật toán chia để trị do John von Neumann đưa ra lần đầu năm 1945.

Ý tưởng của giải thuật này bắt nguồn từ việc trộn 2 danh sách đã sắp xếp thành 1 danh sách mới cũng được sắp.

Giả sử có hai danh sách đã được sắp xếp a[1..m] và b[1..n]. Ta có thể trộn chúng lại thành một danh sách mới c[1..m+n] được sắp xếp theo cách sau:

• So sánh hai phần tử đứng đầu của hai danh sách, lấy phần tử nhỏ hơn cho vào danh sách mới. Tiếp tục như vậy cho tới khi một trong hai danh sách là rỗng.

• Khi một trong hai danh sách là rỗng ta lấy phần còn lại của danh sách kia cho vào cuối danh sách mới.

Ví dụ cho 2 danh sách đã được sắp xếp là a = [1, 4, 6, 7] và b = [2, 3, 8] Ta thực hiện trộn như sau:

2. Các bước thực hiện giải thuật

Đầu tiên, ta coi các phần tử của dãy như các dãy con có 1 phần tử. Tiến hành trộn từng cặp 2 dãy con này để được các dãy con được sắp xếp gồm 2 phần tử. Tiếp tục trộn từng cặp dãy con 2 phần tử thành các dãy con được sắp gồm 4 phần tử... Quá trình được lặp lại cho tới khi toàn bộ dãy được sắp. Ta vẫn thực hiện với dãy trước:

Coi mỗi phần tử của dãy như một dãy con đã sắp gồm 1 phần tử. Tiến hành trộn từng cặp dãy con 1 phần tử với nhau, ta sẽ được dãy:

Sau bước này ta được các dãy con đã sắp gồm 2 phần tử. Tiến hành trộn các cặp dãy con đã sắp gồm 2 phần tử để tạo thành dãy con được sắp gồm 4 phần tử:

Sau bước này ta được dãy con đã sắp gồm 4 phần tử. Tiến hành trộn các cặp dãy con đã sắp, cuối cùng ta được 1 dãy đã sắp xếp như sau:

3. Cài đặt giải thuật

void merge(int array[], int first, int middle, int last) {
    int temp[last + 1];
    int first1, last1, first2, last2;
    int index = first;
        
    first1 = first;
    last1 = middle;
    first2 = middle+1;
    last2 = last;
    
    //so sanh cac phan tu 2 mang con va luu vao mang temp
    while((first1 <= last1) && (first2 <= last2)) {
        if(array[first1] < array[first2]) {
            temp[index] = array[first1];
            index ++;
            first1 ++;                  
        } else {
            temp[index] = array[first2];
            index ++;
            first2 ++;
        }
    }
     
     //neu mang thu 1 chua het
    if(first2 > last2) {
        while(first1 <= last1) {
            temp[index] = array[first1];
            index ++;
            first1 ++;
        }
    }
    
    //neu mang thu 2 chua het
    if(first1 > last1) {
        while(first2 <= last2) {
             temp[index] = array[first2];
             index ++;
             first2 ++;
        }
    }           
        
    for(int i = first; i <= last; i ++) {
        array[i] = temp[i - first];
    }
        
    return;
}

//thuat toan sap xep tron
void mergeSort(int array[], int first, int last) {
    if(first < last) {
        int middle = int((first + last) / 2);
        mergeSort(array, first, middle);
        mergeSort(array, middle + 1, last);
        merge(array, first, middle, last);
    }
}

4. Phân tích

Merge sort là một giải thuật sắp xếp mà có thời gian thực hiện là O(NlogN) trong mọi trường hợp, bởi vậy mà với dữ liệu lớn và cần ít thao tác sắp xếp thì nó sẽ tối ưu hơn Quick sort. Nó chỉ có 1 nhược điểm đó là code hơi khó cài đặt.

1. Cấu trúc dữ liệu và giải thuật: https://docs.google.com/viewer?a=v&pid=sites&srcid=ZGVmYXVsdGRvbWFpbnx2YW5tbDE4MnxneDoxNTFhMGU2NGYzZWIwMmM0
2. Sắp xếp nhanh: https://vi.wikipedia.org/wiki/Sắp_xếp_nhanh
3. Sắp xếp trộn: https://vi.wikipedia.org/wiki/Sắp_xếp_trộn