Cài đặt thuật toán Merge Sort trong lập trình

Merge Sort là một trong những thuật toán sắp xếp nổi tiếng và được sử dụng rộng rãi bởi tính ổn định và hiệu quả của nó. Được tạo ra bởi John von Neumann vào năm 1945, Merge Sort thuộc loại thuật toán chia để trị: nó chia mảng cần sắp xếp thành hai nửa, sắp xếp từng nửa, và sau đó gộp hai nửa đã sắp xếp lại với nhau.

Nguyên lý hoạt động của Merge Sort

1. Chia mảng: Mảng được chia thành hai nửa một cách đệ quy cho tới khi mỗi nửa chỉ còn lại một phần tử.
2. Sắp xếp: Các phần tử trong các nửa nhỏ đã chia được sắp xếp.
3. Gộp lại: Các nửa đã sắp xếp được gộp lại với nhau để tạo thành mảng đã sắp xếp hoàn chỉnh.

Ưu điểm của thuật toán

Một số ưu điểm chính của Merge Sort bao gồm:

• Độ phức tạp ổn định: Merge Sort có độ phức tạp thời gian trong trường hợp tốt nhất, trung bình và xấu nhất đều là (O(n \log n)), trong đó (n) là số phần tử của mảng.
• Tính ổn định: Thuật toán giữ nguyên thứ tự của các phần tử có giá trị bằng nhau sau khi sắp xếp.
• Tính tổng quát: Merge Sort có thể áp dụng cho nhiều loại dữ liệu khác nhau và không phụ thuộc vào chi tiết nhỏ của dữ liệu.

Cài đặt thuật toán Merge Sort

Sau đây là các bước cài đặt Merge Sort trong một số ngôn ngữ lập trình phổ biến.

Python

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

arr = [12, 11, 13, 5, 6, 7]
merge_sort(arr)
print("Mảng đã sắp xếp:", arr)

Java

public class MergeSort {
    public static void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);
            merge(array, left, mid, right);
        }
    }

    public static void merge(int[] array, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] L = new int[n1];
        int[] R = new int[n2];

        for (int i = 0; i < n1; ++i) {
            L[i] = array[left + i];
        }
        for (int j = 0; j < n2; ++j) {
            R[j] = array[mid + 1 + j];
        }

        int i = 0, j = 0;
        int k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                array[k] = L[i];
                i++;
            } else {
                array[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            array[k] = L[i];
            i++;
            k++;
        }

        while (j < n2) {
            array[k] = R[j];
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] array = {12, 11, 13, 5, 6, 7};
        mergeSort(array, 0, array.length - 1);
        System.out.println("Mảng đã sắp xếp: " + Arrays.toString(array));
    }
}

Kết luận

Thuật toán này sở hữu nhiều ưu điểm, đặc biệt là khía cạnh ổn định và hiệu quả đối với các tập dữ liệu lớn. Mặc dù có thể tiêu tốn nhiều bộ nhớ hơn một số thuật toán sắp xếp khác, nhưng ưu điểm về tốc độ và độ ổn định khiến nó trở thành một lựa chọn được ưa dùng trong nhiều tình huống khác nhau. Qua bài viết này, chúng ta đã thấy cách cài đặt Merge Sort bằng các ngôn ngữ lập trình như Python và Java, và hiểu rõ hơn về cách hoạt động của thuật toán này.