Giới Thiệu

Thuật toán Sắp xếp Trộn (Merge Sort) là một trong những thuật toán sắp xếp dựa trên phương pháp chia để trị, được biết đến với tính ổn định và hiệu quả cao. Thuật toán này được phát triển bởi John von Neumann vào năm 1945 và là một trong những phương pháp sắp xếp rất được ưa chuộng nhờ vào hiệu suất ổn định và khả năng hoạt động tốt với các dãy dữ liệu lớn.

Ý Tưởng

Thuật toán Sắp xếp Trộn hoạt động bằng cách chia mảng thành hai nửa, sắp xếp từng nửa một cách độc lập và sau đó trộn hai nửa đã được sắp xếp thành một mảng hoàn chỉnh. Quy trình chia và trộn này được thực hiện đệ quy cho đến khi mảng được chia thành các phần tử đơn lẻ, rồi các phần tử này được trộn lại để tạo thành mảng đã được sắp xếp.

Ví Dụ

Dưới đây là một ví dụ về thuật toán Sắp xếp Trộn được triển khai bằng Java:

public class MergeSortExample {
    // Phương thức để thực hiện sắp xếp trộn
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;

            // Sắp xếp nửa bên trái và bên phải
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

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

    // Phương thức để trộn hai nửa của mảng
    private static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // Tạo các mảng tạm để lưu các phần tử
        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

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

        // Trộn các mảng tạm trở lại vào mảng gốc
        int i = 0, j = 0;
        int k = left;
        while (i < n1 && j < n2) {
            if (leftArray[i] <= rightArray[j]) {
                arr[k] = leftArray[i];
                i++;
            } else {
                arr[k] = rightArray[j];
                j++;
            }
            k++;
        }

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

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

    // Phương thức để in mảng
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] array = {64, 25, 12, 22, 11};

        System.out.println("Mảng ban đầu:");
        printArray(array);

        mergeSort(array, 0, array.length - 1);

        System.out.println("Mảng sau khi sắp xếp:");
        printArray(array);
    }
}

Đánh Giá Thuật Toán Sắp Xếp Trộn

Độ phức tạp thuật toán:

• Trường hợp tốt: O(n log n)
• Trung bình: O(n log n)
• Trường hợp xấu: O(n log n)

Không gian bộ nhớ sử dụng: O(n) (Do cần thêm bộ nhớ để lưu trữ các mảng tạm trong quá trình trộn)

Tại chỗ (In-place): Không (Cần bộ nhớ phụ để lưu các mảng tạm)

Cách sử dụng:

Sắp xếp trộn thường được áp dụng trong các tình huống sau:

• Dữ liệu đầu vào lớn: Khi làm việc với các mảng lớn, thuật toán này cung cấp hiệu suất ổn định và tốt hơn nhiều thuật toán khác như sắp xếp nổi bọt hoặc sắp xếp chọn.
• Yêu cầu sắp xếp ổn định: Khi cần đảm bảo rằng các phần tử có giá trị giống nhau giữ nguyên thứ tự tương đối của chúng sau khi sắp xếp.
• Dữ liệu không thể lưu trữ hoàn toàn trong bộ nhớ: Khi làm việc với dữ liệu lớn hơn bộ nhớ chính, thuật toán có thể được điều chỉnh để hoạt động hiệu quả với các phần dữ liệu nhỏ hơn.

Sắp xếp trộn là một lựa chọn mạnh mẽ cho các ứng dụng cần một thuật toán sắp xếp ổn định và hiệu quả với các dãy dữ liệu lớn, mặc dù nó yêu cầu bộ nhớ phụ để lưu trữ các mảng tạm trong quá trình sắp xếp.