Khóa học CTDL và GT

Bài 15.1: Nguyên lý và cài đặt Merge Sort

Chào mừng các bạn đã quay trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ khám phá một trong những giải thuật sắp xếp kinh điển và mạnh mẽ nhất: Merge Sort (Sắp xếp trộn). Đây là một giải thuật dựa trên nguyên lý "Chia để trị" (Divide and Conquer), nổi tiếng với hiệu suất ổn định và đáng tin cậy, khác biệt với nhiều giải thuật khác có thể bị suy giảm hiệu suất trong trường hợp xấu nhất.

Nếu bạn đã từng tự hỏi làm thế nào để sắp xếp một lượng dữ liệu lớn một cách hiệu quả và đảm bảo, thì Merge Sort chính là câu trả lời. Hãy cùng đi sâu tìm hiểu nguyên lý hoạt động đầy thú vị của nó nhé!

1. Nguyên lý hoạt động của Merge Sort: Chia để trị

Merge Sort hoạt động dựa trên ba bước cốt lõi của nguyên lý Divide and Conquer:

1. Chia (Divide): Liên tục chia mảng/danh sách cần sắp xếp thành hai nửa cho đến khi chỉ còn các mảng con chứa một phần tử. Một mảng chứa một phần tử được coi là đã được sắp xếp.
2. Trị (Conquer): Sắp xếp độc lập các mảng con này (trong Merge Sort, bước này chỉ đơn giản là đạt đến mảng con có 1 phần tử, nó đã được "sắp xếp" sẵn).
3. Kết hợp (Combine/Merge): Trộn (merge) các mảng con đã được sắp xếp lại với nhau để tạo thành các mảng lớn hơn đã được sắp xếp, cho đến khi toàn bộ mảng ban đầu được sắp xếp hoàn chỉnh.

Trái tim của Merge Sort nằm ở bước thứ ba: thủ tục trộn (merge procedure). Đây là nơi hai (hoặc nhiều hơn) mảng con đã được sắp xếp được kết hợp thành một mảng lớn hơn duy nhất, cũng đã được sắp xếp.

2. Đi sâu vào thủ tục Trộn (Merge)

Giả sử chúng ta có hai mảng con đã được sắp xếp:

• Mảng con 1: [1, 3, 5, 7]
• Mảng con 2: [2, 4, 6, 8]

Và chúng ta muốn trộn chúng thành một mảng đã được sắp xếp duy nhất: [1, 2, 3, 4, 5, 6, 7, 8].

Thủ tục trộn hoạt động như sau:

1. Sử dụng con trỏ (hoặc chỉ số) để theo dõi vị trí hiện tại ở mỗi mảng con và ở mảng kết quả (thường là một mảng tạm thời). Bắt đầu các con trỏ ở vị trí đầu tiên của mỗi mảng con.
2. So sánh phần tử mà các con trỏ đang chỉ tới ở hai mảng con.
3. Sao chép phần tử nhỏ hơn vào mảng tạm thời kết quả, và tăng con trỏ của mảng con chứa phần tử vừa được sao chép lên một vị trí. Tăng con trỏ của mảng tạm thời lên một vị trí.
4. Lặp lại bước 2 và 3 cho đến khi một trong hai mảng con đã được sao chép hết các phần tử.
5. Sao chép tất cả các phần tử còn lại từ mảng con kia (mảng chưa hết phần tử) vào mảng tạm thời.
6. Cuối cùng, sao chép toàn bộ các phần tử từ mảng tạm thời trở lại vào vị trí tương ứng trong mảng gốc.

Ví dụ minh họa thủ tục Merge:

Trộn [2, 5, 7] và [3, 6, 9] vào một mảng tạm thời:

Mảng tạm thời [2, 3, 5, 6, 7, 9] sau đó sẽ được sao chép lại vào vị trí ban đầu của hai mảng con trong mảng gốc.

3. Cài đặt Merge Sort bằng C++

Bây giờ, chúng ta sẽ chuyển nguyên lý trên thành code C++. Chúng ta cần hai hàm:

1. Hàm merge: Thực hiện việc trộn hai mảng con đã sắp xếp.
2. Hàm mergeSort: Thực hiện việc chia mảng và gọi đệ quy mergeSort cho các mảng con, sau đó gọi merge để kết hợp kết quả.

#include <iostream>
#include <vector>
#include <algorithm> // Thường không cần thiết cho logic merge sort cơ bản, nhưng hữu ích

// Hàm để trộn hai mảng con đã được sắp xếp
// Mảng con thứ nhất là arr[left...mid]
// Mảng con thứ hai là arr[mid+1...right]
void merge(std::vector<int>& arr, int left, int mid, int right) {
    // Kích thước của hai mảng con
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // Tạo mảng tạm thời để lưu trữ hai mảng con
    // Thay vì tạo hai mảng L và R riêng biệt, chúng ta có thể sử dụng
    // một mảng tạm thời duy nhất có kích thước bằng tổng kích thước
    // của hai mảng con. Điều này giúp giảm số lượng cấp phát bộ nhớ.
    // Tuy nhiên, cách tạo hai mảng L và R rõ ràng hơn trong việc giải thích
    // nguyên lý. Ta sẽ dùng cách tạo 2 mảng tạm cho dễ hiểu.

    // Tạo mảng tạm L[] và R[]
    std::vector<int> L(n1);
    std::vector<int> R(n2);

    // Sao chép dữ liệu từ mảng gốc vào mảng tạm L[] và R[]
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    // Chỉ mục ban đầu của mảng con đầu tiên, mảng con thứ hai, và mảng gốc
    int i = 0; // Chỉ mục ban đầu của mảng con L[]
    int j = 0; // Chỉ mục ban đầu của mảng con R[]
    int k = left; // Chỉ mục ban đầu của mảng gốc arr[] để bắt đầu trộn

    // Trộn các mảng tạm L[] và R[] vào mảng gốc arr[]
    // So sánh các phần tử từ L và R, chọn phần tử nhỏ hơn
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) { // Dấu <= đảm bảo tính ổn định (stable)
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++; // Luôn tăng chỉ mục của mảng gốc
    }

    // Sao chép các phần tử còn lại của mảng L[] (nếu có)
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Sao chép các phần tử còn lại của mảng R[] (nếu có)
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// Hàm đệ quy thực hiện Merge Sort
// arr[] là mảng cần sắp xếp
// left là chỉ mục bắt đầu
// right là chỉ mục kết thúc
void mergeSort(std::vector<int>& arr, int left, int right) {
    // Điều kiện dừng: Nếu mảng con chỉ có 0 hoặc 1 phần tử
    if (left >= right) {
        return; // Đã sắp xếp (mảng 0 hoặc 1 phần tử là tự nó đã sắp xếp)
    }

    // Tìm điểm giữa của mảng
    // Sử dụng left + (right - left) / 2 để tránh tràn số (integer overflow)
    // so với (left + right) / 2 khi left và right rất lớn
    int mid = left + (right - left) / 2;

    // Gọi đệ quy mergeSort cho nửa bên trái
    mergeSort(arr, left, mid);

    // Gọi đệ quy mergeSort cho nửa bên phải
    mergeSort(arr, mid + 1, right);

    // Trộn hai nửa đã được sắp xếp lại với nhau
    merge(arr, left, mid, right);
}

// Hàm tiện ích để in mảng (không bắt buộc, chỉ để kiểm tra)
void printArray(const std::vector<int>& arr) {
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
}

// Chương trình chính để minh họa
int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6, 7};
    int arr_size = arr.size();

    std::cout << "Mang ban dau:" << std::endl;
    printArray(arr);

    // Bắt đầu sắp xếp từ chỉ mục 0 đến kích thước - 1
    mergeSort(arr, 0, arr_size - 1);

    std::cout << "\nMang sau khi sap xep boi Merge Sort:" << std::endl;
    printArray(arr);

    // Ví dụ khác phức tạp hơn một chút
    std::vector<int> arr2 = {38, 27, 43, 3, 9, 82, 10};
    int arr2_size = arr2.size();

    std::cout << "\nMang ban dau (vi du 2):" << std::endl;
    printArray(arr2);

    mergeSort(arr2, 0, arr2_size - 1);

    std::cout << "\nMang sau khi sap xep boi Merge Sort (vi du 2):" << std::endl;
    printArray(arr2);


    return 0;
}

4. Giải thích Code C++

• Hàm merge(std::vector<int>& arr, int left, int mid, int right):

  • Tham số: Nhận mảng arr, chỉ mục bắt đầu left, chỉ mục giữa mid, và chỉ mục kết thúc right của phần mảng cần trộn. Chú ý arr được truyền bằng tham chiếu (&) để có thể thay đổi trực tiếp mảng gốc.
  • n1, n2: Tính kích thước của hai mảng con bên trái (left đến mid) và bên phải (mid+1 đến right).
  • std::vector<int> L(n1), R(n2);: Tạo hai mảng tạm L và R để lưu trữ dữ liệu của hai mảng con.
  • Hai vòng lặp for: Sao chép dữ liệu từ arr vào hai mảng tạm L và R.
  • int i = 0, j = 0; int k = left;: Khởi tạo các chỉ mục. i cho mảng L, j cho mảng R, và k cho vị trí hiện tại trong mảng gốc arr mà ta sẽ ghi vào.
  • Vòng lặp while (i < n1 && j < n2): Đây là trái tim của thủ tục trộn. Nó so sánh phần tử hiện tại của L (L[i]) và R (R[j]). Phần tử nào nhỏ hơn (hoặc bằng để đảm bảo tính ổn định), sẽ được sao chép vào arr[k]. Sau đó, chỉ mục tương ứng (i hoặc j) và chỉ mục k đều tăng lên.
  • Hai vòng lặp while còn lại: Sau khi một trong hai mảng L hoặc R đã hết phần tử, vòng lặp chính sẽ dừng. Các vòng lặp này có nhiệm vụ sao chép nốt tất cả các phần tử còn lại từ mảng con chưa hết vào mảng gốc arr.
  • Sau khi hàm merge hoàn thành, phần của mảng gốc từ left đến right đã được sắp xếp.

• Hàm mergeSort(std::vector<int>& arr, int left, int right):

  • Tham số: Nhận mảng arr (tham chiếu), chỉ mục bắt đầu left, và chỉ mục kết thúc right.
  • if (left >= right) return;: Đây là điều kiện dừng của đệ quy. Khi left lớn hơn hoặc bằng right, điều đó có nghĩa là mảng con hiện tại chỉ chứa 0 hoặc 1 phần tử. Một mảng con như vậy hiển nhiên đã được sắp xếp, nên ta dừng đệ quy cho nhánh này.
  • int mid = left + (right - left) / 2;: Tính chỉ mục giữa. Công thức này giúp tránh tràn số khi left và right là các số nguyên rất lớn.
  • mergeSort(arr, left, mid);: Gọi đệ quy để sắp xếp nửa bên trái của mảng con hiện tại. Khi lệnh này kết thúc, phần arr[left...mid] được đảm bảo đã sắp xếp.
  • mergeSort(arr, mid + 1, right);: Gọi đệ quy để sắp xếp nửa bên phải của mảng con hiện tại. Khi lệnh này kết thúc, phần arr[mid+1...right] được đảm bảo đã sắp xếp.
  • merge(arr, left, mid, right);: Sau khi cả hai nửa trái và phải đã được sắp xếp độc lập thông qua các lệnh gọi đệ quy, hàm merge được gọi để trộn hai nửa đã sắp xếp này lại thành một mảng con duy nhất đã được sắp xếp, bao phủ toàn bộ phạm vi từ left đến right.

• Hàm printArray và main:

  • printArray: Một hàm tiện ích đơn giản để hiển thị nội dung của mảng.
  • main: Nơi chương trình bắt đầu. Nó tạo một vector, in ra trạng thái ban đầu, gọi mergeSort với toàn bộ phạm vi của vector (từ 0 đến kích thước - 1), và sau đó in ra vector đã được sắp xếp.

5. Phân tích độ phức tạp

Hiểu rõ độ phức tạp là điều quan trọng để biết khi nào nên sử dụng Merge Sort.

• Độ phức tạp về Thời gian (Time Complexity):

  • Merge Sort luôn chia mảng thành hai nửa bằng nhau. Số lần chia cần thiết để đạt được mảng con 1 phần tử là log base 2 của n, hay O(log n), trong đó n là kích thước mảng. Đây là chiều sâu của cây đệ quy.
  • Tại mỗi cấp của cây đệ quy (trừ cấp lá), chúng ta thực hiện thủ tục merge trên các mảng con. Tổng số phần tử được xử lý bởi thủ tục merge ở mỗi cấp luôn là n (ví dụ: ở cấp trên cùng là trộn 2 mảng n/2, ở cấp dưới hơn là trộn 4 mảng n/4, tổng cộng vẫn là n). Thủ tục merge cho hai mảng con có tổng kích thước k mất O(k) thời gian vì nó chỉ duyệt qua các phần tử một lần. Do đó, tổng thời gian cho việc trộn ở mỗi cấp là O(n).
  • Tổng thời gian = (Số cấp đệ quy) (Thời gian trộn mỗi cấp) = **O(log n) O(n) = O(n log n)**.
  • Điều đặc biệt là độ phức tạp O(n log n) này là như nhau cho trường hợp tốt nhất, trung bình và xấu nhất. Đây là ưu điểm lớn của Merge Sort so với các thuật toán như Quick Sort (có thể tệ nhất là O(n^2)).

• Độ phức tạp về Không gian (Space Complexity):

  • Hàm merge cần một hoặc hai mảng tạm thời để lưu trữ các phần tử trong quá trình trộn. Trong cài đặt trên, chúng ta dùng hai mảng tạm L và R có tổng kích thước là n1 + n2 = (mid - left + 1) + (right - mid) = right - left + 1, tức là kích thước của mảng con hiện tại đang xử lý. Ở cấp trên cùng của đệ quy, mảng con này có kích thước n. Do đó, Merge Sort yêu cầu không gian phụ O(n) cho mảng tạm.
  • Không gian cho stack đệ quy cũng cần xem xét, nhưng với chiều sâu O(log n), nó chỉ tốn O(log n) không gian, thường ít hơn đáng kể so với không gian O(n) của mảng tạm.
  • Vì vậy, độ phức tạp về không gian của Merge Sort là O(n). Đây là một nhược điểm so với các thuật toán "in-place" như Heap Sort hoặc phiên bản tối ưu của Quick Sort, chỉ cần O(log n) hoặc O(1) không gian phụ (cho stack đệ quy hoặc không).

6. Ưu điểm và Nhược điểm

• Ưu điểm:

  • Độ phức tạp thời gian ổn định: Luôn là O(n log n), bất kể dữ liệu ban đầu được sắp xếp như thế nào. Rất phù hợp khi cần đảm bảo hiệu suất.
  • Ổn định (Stable): Merge Sort là một giải thuật sắp xếp ổn định. Điều này có nghĩa là nó giữ nguyên thứ tự tương đối của các phần tử bằng nhau. Nếu có hai phần tử có giá trị bằng nhau, phần tử xuất hiện trước trong mảng gốc sẽ vẫn xuất hiện trước trong mảng đã sắp xếp.
  • Hiệu quả cho danh sách liên kết: Merge Sort rất phù hợp để sắp xếp danh sách liên kết vì thủ tục trộn có thể được thực hiện mà không cần mảng tạm riêng biệt chỉ bằng cách thay đổi các con trỏ, giúp tiết kiệm chi phí sao chép dữ liệu.

• Nhược điểm:

  • Yêu cầu không gian phụ O(n): Đây là nhược điểm đáng kể nhất. Nó cần bộ nhớ phụ bằng kích thước của mảng gốc (hoặc ít nhất là bằng nửa mảng gốc tùy cài đặt). Với các tập dữ liệu rất lớn trên hệ thống có bộ nhớ hạn chế, điều này có thể là vấn đề.
  • Thủ tục trộn có thể chậm hơn cho mảng nhỏ: Đối với các mảng rất nhỏ, chi phí quản lý đệ quy và thủ tục trộn có thể khiến Merge Sort chậm hơn các thuật toán đơn giản hơn như Insertion Sort.
  • Không "in-place" theo định nghĩa chặt chẽ: Mặc dù có thể tối ưu không gian, phiên bản phổ biến và dễ cài đặt nhất không phải là "in-place" do cần mảng tạm.

7. Khi nào nên sử dụng Merge Sort?

Merge Sort là một lựa chọn tuyệt vời khi:

• Bạn cần một giải thuật sắp xếp với hiệu suất đảm bảo O(n log n) trong mọi trường hợp.
• Tính ổn định của thứ tự sắp xếp là yêu cầu bắt buộc.
• Bạn đang làm việc với danh sách liên kết hoặc các cấu trúc dữ liệu mà việc truy cập tuần tự hiệu quả hơn truy cập ngẫu nhiên.
• Bạn cần sắp xếp dữ liệu quá lớn không thể chứa hoàn toàn trong bộ nhớ chính (gọi là sắp xếp ngoài - external sorting).

Bài tập ví dụ:

Tổng chữ số

Trong một buổi họp kỹ thuật, FullHouse Dev được giám đốc kỹ thuật đưa ra một bài toán thú vị để rèn luyện tư duy logic. Bài toán này yêu cầu họ phải tính toán số lần thay đổi tối thiểu để cân bằng tổng các chữ số trong một chuỗi số. Với sự sáng tạo, FullHouse Dev đã bắt tay vào giải quyết thử thách này.

Bài toán

Cho một chuỗi \(S\) có độ dài \(2N\) chỉ gồm các chữ số từ 0 đến 9. Bạn có thể thực hiện một thao tác là chọn một vị trí bất kỳ và thay thế chữ số ở vị trí đó bằng một chữ số khác từ 0 đến 9. Nhiệm vụ của bạn là xác định số lần thao tác tối thiểu cần thực hiện để tổng của \(N\) chữ số đầu tiên bằng tổng của \(N\) chữ số tiếp theo.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case.
• Với mỗi test case:
  • Dòng đầu tiên chứa một số nguyên \(N\).
  • Dòng tiếp theo chứa một chuỗi \(S\) có độ dài \(2N\).

OUTPUT FORMAT:

• Với mỗi test case, in ra số lần thao tác tối thiểu cần thực hiện trên một dòng mới.

Ràng buộc:

• \(1 \leq T \leq 100\)
• \(1 \leq N \leq 10^5\)
• \(S\) chỉ chứa các chữ số từ 0 đến 9

Ví dụ

INPUT

1
2
1325

OUTPUT

1

Giải thích

Ở test case này:

• \(N = 2\)
• \(S = 1325\)

FullHouse Dev có thể thực hiện một thao tác:

• Thay đổi \(S[1]\) từ 1 thành 4. Sau khi thay đổi, \(S = 4325\).

Khi đó, tổng của \(S[1]\) đến \(S[2]\) = 4 + 3 = 7 và tổng của \(S[3]\) đến \(S[4]\) = 2 + 5 = 7.

Vì vậy, số lần thao tác tối thiểu cần thực hiện là 1.

Lưu ý: Có thể có các cách khác để đạt được kết quả, nhưng không thể thực hiện ít hơn 1 thao tác để đạt được yêu cầu. Tuyệt vời, đây là hướng dẫn ngắn gọn để giải bài này bằng C++:

1. Mục tiêu: Cần tìm số thao tác tối thiểu để tổng N chữ số đầu tiên bằng tổng N chữ số tiếp theo.
2. Tính tổng ban đầu: Đầu tiên, tính tổng của N chữ số đầu tiên (gọi là sum1) và tổng của N chữ số tiếp theo (gọi là sum2). Duyệt qua chuỗi S, từ S[0] đến S[N-1] để tính sum1, và từ S[N] đến S[2N-1] để tính sum2. Nhớ chuyển ký tự chữ số sang giá trị số nguyên (ví dụ: S[i] - '0').
3. Tính chênh lệch: Tìm trị tuyệt đối của hiệu hai tổng: diff = abs(sum1 - sum2). Đây là "lượng" tổng cần cân bằng.
4. Phân tích thao tác: Một thao tác là thay đổi một chữ số bất kỳ. Khi thay đổi một chữ số d_old thành d_new, tổng của nửa đó thay đổi một lượng là d_new - d_old.
5. Hiệu quả tối đa của một thao tác: Để giảm số thao tác, mỗi thao tác nên đóng góp nhiều nhất có thể vào việc giảm diff.
   • Nếu sum1 > sum2, ta cần giảm sum1 hoặc tăng sum2. Giảm sum1 tối đa bằng cách đổi '9' thành '0' (-9). Tăng sum2 tối đa bằng cách đổi '0' thành '9' (+9). Cả hai đều làm giảm sum1 - sum2 (hoặc tăng sum2 - sum1) một lượng tối đa là 9.
   • Nếu sum1 < sum2, ta cần tăng sum1 hoặc giảm sum2. Tăng sum1 tối đa bằng cách đổi '0' thành '9' (+9). Giảm sum2 tối đa bằng cách đổi '9' thành '0' (-9). Cả hai đều làm tăng sum1 - sum2 (hoặc giảm sum2 - sum1) một lượng tối đa là 9.
   • Như vậy, một thao tác có thể làm giảm trị tuyệt đối của chênh lệch |sum1 - sum2| tối đa là 9.
6. Số thao tác tối thiểu: Số thao tác tối thiểu cần thiết để giảm chênh lệch diff về 0 là diff chia cho hiệu quả tối đa của một thao tác (là 9), làm tròn lên. Công thức tính làm tròn lên ceil(a/b) cho số nguyên dương a, b là (a + b - 1) / b khi dùng phép chia nguyên. Vậy, số thao tác tối thiểu = (diff + 9 - 1) / 9 hay (diff + 8) / 9 sử dụng phép chia nguyên.
7. Cấu trúc code:
   • Đọc số test case T.
   • Lặp T lần:
     • Đọc N.
     • Đọc chuỗi S.
     • Tính sum1 và sum2.
     • Tính diff = abs(sum1 - sum2).
     • Tính và in kết quả (diff + 8) / 9.

Làm thêm nhiều bài tập miễn phí tại đây