CTDL và giải thuật - Sắp xếp trộn (Merge Sort)

Nhập vào số nguyên dương n, tiếp theo là n số nguyên của dãy số a.
Hãy sắp xếp dãy số a thành dãy không giảm (số sau không bé hơn số trước) và in dãy đó ra màn hình, sau mỗi phần tử có đúng một khoảng trắng.

Ví dụ:

  • Test mẫu 1:
     
    Input Output

    5
    1 3 2 5 2

    1 2 2 3 5

    Với a = [1, 3, 2, 5, 2] thì kết quả mong muốn là:
    "1 2 2 3 5 ".
     
  • Test mẫu 2:
     
    Input Output

    5
    3 2 1 4 5

    1 2 3 4 5

    Với a = [3, 2, 1, 4, 5] thì kết quả mong muốn là:
    "1 2 3 4 5 ".

Lý thuyết.

Giới thiệu giải thuật sắp xếp trộn (Merge Sort).

Sắp xếp trộn (Merge Sort) là một giải thuật sắp xếp dựa trên giải thuật Chia để trị (Divide and Conquer). Với độ phức tạp thời gian trường hợp xấu nhất là Ο(n log n) thì đây là một trong các giải thuật đáng được quan tâm nhất.

Đầu tiên, giải thuật sắp xếp trộn chia mảng thành hai nửa và sau đó kết hợp chúng lại với nhau thành một mảng đã được sắp xếp.

Ý tưởng thuật toán.

mergeSort(a[], l,  r)
if r > l
     1. Tìm chỉ số nằm giữa mảng để chia mảng thành 2 nửa:
             middle m = (l+r)/2
     2. Gọi đệ quy hàm mergeSort cho nửa đầu tiên:  
             mergeSort(a, l, m)
     3. Gọi đệ quy hàm mergeSort cho nửa thứ hai:
             mergeSort(a, m+1, r)
     4. Gộp 2 nửa mảng đã sắp xếp ở (2) và (3):
             merge(a, l, m, r)

Hình ảnh ví dụ:

Hình ảnh trên hiển thị cho bạn toàn bộ sơ đồ tiến trình của thuật toán merge sort cho mảng [5, 4, 6, 1, 2, 7, 3]. Nếu nhìn kỹ hơn vào sơ đồ này, chúng ta có thể thấy mảng ban đầu được lặp lại hành động chia cho tới khi kích thước các mảng sau chia là 1. Khi kích thước các mảng con là 1, tiến trình gộp sẽ bắt đầu thực hiện gộp lại các mảng này cho tới khi hoàn thành và chỉ còn một mảng đã sắp xếp.

Để xem rõ hơn về thuật toán ghép 2 dãy lại bạn có thể xem tại đây.

 

Hướng dẫn bài tập.

Code mẫu:

Ngôn ngữ C++:

#include<iostream>
 
using namespace std;

void merge(int arr[], int l, int m, int r){
    int i, j, k;
    int n1 = m - l + 1;
    int n2 =  r - m;
    int L[n1], R[n2];
    for (i = 0; i < n1; i++){
    	L[i] = arr[l + i];
	}  
    for (j = 0; j < n2; j++){
    	R[j] = arr[m + 1+ j];
	}
    i = 0;
    j = 0; 
    k = l; 
    while (i < n1 && j < n2){
        if (L[i] <= R[j]){
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1){
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2){
        arr[k] = R[j];
        j++;
        k++;
    }
}
void mergeSort(int a[], int l, int r){
    if (l < r){
        int m = l+(r-l)/2;
        mergeSort(a, l, m);
        mergeSort(a, m+1, r);
        merge(a, l, m, r);
    }
}
 
void printArray(int a[], int n){
    for (int i = 0; i < n; i++){
    	cout << a[i] << " ";
	}
}
int a[100001];
int main(){
	int n;
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> a[i];
	}
    mergeSort(a, 0, n - 1);
    printArray(a, n);
    
    return 0;
}