Chương trình C++ triển khai thuật toán Merge Sort (Sắp xếp trộn)

Kỹ thuật sắp xếp trộn (Merge Sort) dựa trên kỹ thuật chia để trị (divide and conquer). Chúng ta chia toàn bộ tập dữ liệu thành các phần nhỏ hơn và trộn chúng thành một phần lớn hơn theo thứ tự đã sắp xếp. Nó cũng rất hiệu quả cho trường hợp xấu nhất vì thuật toán này có độ phức tạp thời gian thấp cho trường hợp xấu nhất.

Độ phức tạp của kỹ thuật Merge Sort

• Độ phức tạp thời gian: O(n log n) cho mọi trường hợp
• Độ phức tạp không gian: O(n)

Đầu vào — Danh sách chưa sắp xếp: 14 20 78 98 20 45
Đầu ra — Mảng sau khi sắp xếp: 14 20 20 45 78 98

Thuật toán

merge(array, left, middle, right)

Đầu vào: Mảng tập dữ liệu, chỉ số left, middle và right

Đầu ra: Danh sách đã trộn

Bắt đầu
    nLeft := m - left + 1
    nRight := right – m
    Định nghĩa mảng leftArr và rightArr kích thước nLeft và nRight
    for i := 0 đến nLeft
        leftArr[i] := array[left + i]
    for j := 0 đến nRight
        rightArr[j] := array[middle + j + 1]
    i := 0, j := 0, k := left
    while i < nLeft VÀ j < nRight
        if leftArr[i] <= rightArr[j] thì
            array[k] = leftArr[i]
            i := i+1
        else
            array[k] = rightArr[j]
            j := j+1
        k := k+1
    while i < nLeft
        array[k] := leftArr[i]
        i := i+1
        k := k+1
    while j < nRight
        array[k] := rightArr[j]
        j := j+1
        k := k+1
Kết thúc

mergeSort(array, left, right)

Đầu vào: Mảng dữ liệu, và giới hạn dưới, trên của mảng

Đầu ra: Mảng đã sắp xếp

Bắt đầu
    if left < right thì
        mid := left + (right - left) / 2
        mergeSort(array, left, mid)
        mergeSort(array, mid+1, right)
        merge(array, left, mid, right)
Kết thúc

Mã ví dụ

#include <iostream>
using namespace std;

void swapping(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

void display(int *array, int size) {
    for(int i = 0; i < size; i++)
        cout << array[i] << " ";
    cout << endl;
}

void merge(int *array, int l, int m, int r) {
    int i, j, k, nl, nr;
    nl = m - l + 1; nr = r - m;
    int larr[nl], rarr[nr];
    for(i = 0; i < nl; i++)
        larr[i] = array[l + i];
    for(j = 0; j < nr; j++)
        rarr[j] = array[m + 1 + j];
    i = 0; j = 0; k = l;
    while(i < nl && j < nr) {
        if(larr[i] <= rarr[j]) {
            array[k] = larr[i];
            i++;
        } else {
            array[k] = rarr[j];
            j++;
        }
        k++;
    }
    while(i < nl) {
        array[k] = larr[i];
        i++; k++;
    }
    while(j < nr) {
        array[k] = rarr[j];
        j++; k++;
    }
}

void mergeSort(int *array, int l, int r) {
    if(l < r) {
        int m = l + (r - l) / 2;
        mergeSort(array, l, m);
        mergeSort(array, m + 1, r);
        merge(array, l, m, r);
    }
}

int main() {
    int n;
    cout << "Nhập số lượng phần tử: ";
    cin >> n;
    int arr[n];
    cout << "Nhập các phần tử:" << endl;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << "Mảng trước khi sắp xếp: ";
    display(arr, n);
    mergeSort(arr, 0, n-1);
    cout << "Mảng sau khi sắp xếp: ";
    display(arr, n);
}

Kết quả đầu ra

Nhập số lượng phần tử: 6
Nhập các phần tử: 14 20 78 98 20 45
Mảng trước khi sắp xếp: 14 20 78 98 20 45
Mảng sau khi sắp xếp: 14 20 20 45 78 98