Toán tin vuotlen.com

Thuật toán sắp xếp trộn (Merge Sort)

Phân loại: Giải thuật sắp xếp ngoài ram, sắp xếp chia để trị (divide and conquer). Nó chia mảng thành hai nửa, sắp xếp từng nửa, và sau đó hợp nhất hai nửa đã sắp xếp lại với nhau.

Cấu trúc dữ liệu: Ngẫu nhiên.
Độ phức tạp thời gian (Time Complexity): Trường hợp xấu nhất (Worst Case) O(n log n).

Độ phức tạp dung lượng (Space Complexity): O(n) vì cần lưu trữ tất cả các phần tử trong bộ nhớ khi chia và hợp nhất.

Độ phức tạp bộ nhớ (Memory Complexity): O(n).

Giải thích chi tiết:

  1. Chia (Divide):

    • Mảng ban đầu được chia liên tiếp cho đến khi mỗi mảng con chỉ còn một phần tử (hoặc không còn phần tử nào), khi đó mỗi mảng con coi như đã được sắp xếp.

  2. Trị (Conquer):

    • Sắp xếp từng nửa mảng bằng cách áp dụng Merge Sort đệ quy. Điều này tiếp tục cho đến khi toàn bộ mảng được chia nhỏ hoàn toàn.

  3. Hợp (Combine):

    • Sau khi các mảng con đã được sắp xếp, chúng được hợp nhất lại theo thứ tự bằng cách so sánh từng phần tử của hai mảng con và sắp xếp chúng vào vị trí đúng trong mảng ban đầu. Điều này đảm bảo rằng mỗi bước hợp nhất tạo ra một mảng đã sắp xếp.

Psudocode externalMergeSort (bản tối ưu của Merge Sort):

SortChunk(data, l, r)
    sort(data.begin() + l, data.begin() + r)        // Sắp xếp mảng từ vị trí l đến r

ExternalMergeSort(data, chunkSize)
    SplitAndSortChunks(data, chunkSize)               // Chia dữ liệu thành các khối nhỏ và sắp xếp từng khối

    length = chunkSize                                // Khởi tạo độ dài của khối bằng kích thước khối ban đầu
    n = size of data                                  // Lấy kích thước của mảng dữ liệu
    while length < n do                               // Tiếp tục hợp nhất các khối cho đến khi toàn bộ mảng được hợp nhất
        for i = 0 to n by 2 * length do               // Duyệt qua mảng dữ liệu với bước nhảy là 2 * length
            l1 = i                                    // Bắt đầu của khối đầu tiên
            r1 = min(i + length, n)                   // Kết thúc của khối đầu tiên
            l2 = r1                                   // Bắt đầu của khối thứ hai
            r2 = min(i + 2 * length, n)               // Kết thúc của khối thứ hai
            MergeChunks(data, l1, r1, l2, r2)         // Hợp nhất hai khối đã sắp xếp
        end for
        length = 2 * length                           // Tăng gấp đôi độ dài của khối sau mỗi lần hợp nhất
    end while
end function

SplitAndSortChunks(data, chunkSize)
    n = size of data                                  // Lấy kích thước của mảng dữ liệu
    for i = 0 to n by chunkSize do                    // Duyệt qua mảng dữ liệu với bước nhảy là chunkSize
        SortChunk(data, i, min(i + chunkSize, n))     // Sắp xếp từng khối nhỏ từ vị trí i đến vị trí min(i + chunkSize, n)
    end for
end function

MergeChunks(data, l1, r1, l2, r2)
    mergedChunk = empty array of size (r1 - l1 + r2 - l2) // Tạo mảng tạm thời để lưu trữ kết quả hợp nhất

    i = l1                                            // Khởi tạo chỉ số cho khối đầu tiên
    j = l2                                            // Khởi tạo chỉ số cho khối thứ hai
    while i < r1 and j < r2 do                        // So sánh các phần tử của hai khối và hợp nhất chúng
        if data[i] < data[j] then
            append data[i] to mergedChunk             // Thêm phần tử nhỏ hơn vào mergedChunk
            i = i + 1                                 // Tăng chỉ số i
        else
            append data[j] to mergedChunk             // Thêm phần tử nhỏ hơn vào mergedChunk
            j = j + 1                                 // Tăng chỉ số j
        end if
    end while

    while i < r1 do                                   // Thêm các phần tử còn lại của khối đầu tiên vào mergedChunk
        append data[i] to mergedChunk
        i = i + 1
    end while

    while j < r2 do                                   // Thêm các phần tử còn lại của khối thứ hai vào mergedChunk
        append data[j] to mergedChunk
        j = j + 1
    end while

    copy mergedChunk to data[l1 to r2]                // Sao chép mergedChunk trở lại mảng dữ liệu
end function

 

Giải thích từng bước:

  1. externalMergeSort(data, chunkSize):

    • Chia mảng dữ liệu thành các khối nhỏ và sắp xếp từng khối nhỏ.
    • Bắt đầu hợp nhất các khối đã sắp xếp với độ dài length bằng chunkSize.
    • Tiếp tục tăng gấp đôi độ dài các khối và hợp nhất cho đến khi toàn bộ mảng được sắp xếp.

  2. splitAndSortChunks(data, chunkSize):

    • Chia mảng data thành các khối có kích thước chunkSize.
    • Sắp xếp từng khối nhỏ bằng cách gọi hàm sortChunk.

  3. sortChunk(data, l, r):

    • Sắp xếp phần mảng data từ chỉ số l đến chỉ số r-1.

  4. mergeChunks(data, l1, r1, l2, r2):

    • Hợp nhất hai phần mảng đã sắp xếp từ l1 đến r1-1 và từ l2 đến r2-1.
    • Tạo danh sách trống mergedChunk để chứa các phần tử đã hợp nhất.
    • Thêm các phần tử từ hai phần mảng vào mergedChunk theo thứ tự tăng dần.
    • Sao chép mergedChunk trở lại mảng data từ chỉ số l1 đến r2-1.

Ví dụ minh họa:

1. Chia và sắp xếp các khối:
   Input: {14, 33, 27, 10, 35, 20, 5, 19, 42, 44}
   ChunkSize: 3

   Chia mảng thành các khối nhỏ và sắp xếp:
   Khối 1: {14, 33, 27} -> Sắp xếp: {14, 27, 33}
   Khối 2: {10, 35, 20} -> Sắp xếp: {10, 20, 35}
   Khối 3: {5, 19, 42}  -> Sắp xếp: {5, 19, 42}
   Khối 4: {44}         -> Sắp xếp: {44}

   Mảng sau khi sắp xếp các khối:
   {14, 27, 33, 10, 20, 35, 5, 19, 42, 44}

2. Hợp nhất các khối đã sắp xếp:
   Length = 3

   Lần hợp nhất 1:
   Hợp nhất Khối 1: {14, 27, 33} và Khối 2: {10, 20, 35} -> Kết quả: {10, 14, 20, 27, 33, 35}
   Hợp nhất Khối 3: {5, 19, 42} và Khối 4: {44}          -> Kết quả: {5, 19, 42, 44}

   Mảng sau lần hợp nhất này:
   {10, 14, 20, 27, 33, 35, 5, 19, 42, 44}

   Lần hợp nhất 2:
   Hợp nhất khối {10, 14, 20, 27, 33, 35} và khối {5, 19, 42, 44} -> Kết quả: {5, 10, 14, 19, 20, 27, 33, 35, 42, 44}

   Mảng cuối cùng đã được sắp xếp:
   {5, 10, 14, 19, 20, 27, 33, 35, 42, 44}

code C++:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// Hàm sắp xếp trên mảng data từ l đến r (đã bao gồm r)
void sortChunk(vector<int>& data, int l, int r) {
    sort(data.begin() + l, data.begin() + r);
}

// Hàm chia mảng thành các khối nhỏ và sắp xếp mỗi khối
void splitAndSortChunks(vector<int>& data, int chunkSize) {
    int n = data.size();
    for (int i = 0; i < n; i += chunkSize) {
        sortChunk(data, i, min(i + chunkSize, n));
    }
}

// Hàm hợp nhất hai mảng đã sắp xếp data1 và data2 vào data
void mergeChunks(vector<int>& data, int l1, int r1, int l2, int r2) {
    vector<int> mergedChunk;
    mergedChunk.reserve(r1 - l1 + r2 - l2);

    int i = l1, j = l2;
    while (i < r1 && j < r2) {
        if (data[i] < data[j]) {
            mergedChunk.push_back(data[i++]);
        } else {
            mergedChunk.push_back(data[j++]);
        }
    }

    while (i < r1) {
        mergedChunk.push_back(data[i++]);
    }
    while (j < r2) {
        mergedChunk.push_back(data[j++]);
    }

    copy(mergedChunk.begin(), mergedChunk.end(), data.begin() + l1);
}

// External Merge Sort
void externalMergeSort(vector<int>& data, int chunkSize) {
    splitAndSortChunks(data, chunkSize);

    int length = chunkSize;
    int n = data.size();
    while (length < n) {
        for (int i = 0; i < n; i += 2 * length) {
            int l1 = i;
            int r1 = min(i + length, n);
            int l2 = r1;
            int r2 = min(i + 2 * length, n);
            mergeChunks(data, l1, r1, l2, r2);
        }
        length *= 2;
    }
}

int main() {
    vector<int> data = {14, 33, 27, 10, 35, 20, 5, 19, 42, 44};
    int chunkSize = 3;

    externalMergeSort(data, chunkSize);

    cout << "Du lieu da sap xep: ";
    for (int num : data) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}