Giải Thuật Sắp Xếp Nâng Cao: Merge Sort & Quick Sort

Chào mừng bạn đến với bài viết số 12 trong series về cấu trúc dữ liệu và giải thuật. Hôm nay, chúng ta sẽ khám phá hai thuật toán sắp xếp mạnh mẽ: Merge Sort và Quick Sort. Cả hai đều thuộc nhóm sắp xếp nâng cao, hiệu quả hơn so với các thuật toán cơ bản như Bubble Sort hay Insertion Sort.

1. Sắp Xếp Trộn (Merge Sort)

Merge Sort là một thuật toán sắp xếp dựa trên nguyên lý "chia để trị" (Divide and Conquer). Nó hoạt động bằng cách chia nhỏ mảng ban đầu thành các mảng con nhỏ hơn. Sau đó, các mảng con này được sắp xếp độc lập. Cuối cùng, chúng được trộn lại với nhau để tạo thành một mảng đã sắp xếp hoàn chỉnh.

1.1. Nguyên Lý "Chia Để Trị" (Divide and Conquer)

"Chia để trị" là một chiến lược giải quyết vấn đề hiệu quả. Nó bao gồm ba bước chính:

• Chia (Divide): Chia bài toán lớn thành các bài toán con nhỏ hơn, tương tự.
• Trị (Conquer): Giải quyết các bài toán con một cách đệ quy. Nếu bài toán con đủ nhỏ, giải trực tiếp.
• Kết hợp (Combine): Kết hợp các kết quả của các bài toán con để tạo ra lời giải cho bài toán ban đầu.

Trong Merge Sort, chúng ta chia mảng thành hai nửa. Tiếp tục chia đến khi mỗi mảng chỉ còn một phần tử (đã được sắp xếp). Sau đó, chúng ta trộn các mảng con đã sắp xếp lại với nhau.

1.2. Ví Dụ Minh Họa trong Java

Dưới đây là một ví dụ triển khai Merge Sort bằng Java:

public class MergeSort {

    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;

            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            merge(arr, left, mid, right);
        }
    }

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

        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

        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];

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (leftArray[i] <= rightArray[j]) {
                arr[k] = leftArray[i];
                i++;
            } else {
                arr[k] = rightArray[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = leftArray[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = rightArray[j];
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        mergeSort(arr, 0, arr.length - 1);

        System.out.println("Mảng đã sắp xếp:");
        for (int i = 0; i < arr.length; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
}

1.3. Độ Phức Tạp và Ưu Điểm

Merge Sort có độ phức tạp thời gian là O(n log n) trong mọi trường hợp (tốt nhất, trung bình, xấu nhất). Đây là một ưu điểm lớn so với các thuật toán có độ phức tạp O(n^2) trong trường hợp xấu nhất. Tuy nhiên, Merge Sort cần thêm không gian bộ nhớ để lưu trữ các mảng con tạm thời.

Ưu điểm:

• Độ phức tạp thời gian ổn định O(n log n).
• Thích hợp cho việc sắp xếp các danh sách liên kết.

Nhược điểm:

• Cần thêm không gian bộ nhớ.
• Có thể chậm hơn Quick Sort trong thực tế (tùy thuộc vào dữ liệu).

2. Sắp Xếp Nhanh (Quick Sort)

Quick Sort cũng là một thuật toán sắp xếp dựa trên nguyên lý "chia để trị". Tuy nhiên, cách tiếp cận của nó khác với Merge Sort. Quick Sort chọn một phần tử làm "pivot" (chốt). Sau đó, nó chia mảng thành hai phần: một phần chứa các phần tử nhỏ hơn pivot và một phần chứa các phần tử lớn hơn pivot. Quá trình này được thực hiện đệ quy trên hai phần này.

2.1. Nguyên Lý Hoạt Động

Quick Sort hoạt động theo các bước sau:

1. Chọn Pivot: Chọn một phần tử làm pivot. Có nhiều cách chọn pivot, ví dụ: chọn phần tử đầu tiên, phần tử cuối cùng, hoặc phần tử ngẫu nhiên.
2. Phân Vùng (Partitioning): Sắp xếp lại mảng sao cho tất cả các phần tử nhỏ hơn pivot nằm bên trái pivot, và tất cả các phần tử lớn hơn pivot nằm bên phải pivot.
3. Đệ Quy (Recursion): Gọi đệ quy Quick Sort trên hai phần con bên trái và bên phải pivot.

2.2. Ví Dụ Minh Họa trong Java

Dưới đây là một ví dụ triển khai Quick Sort bằng Java:

public class QuickSort {

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);

            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = (low - 1);
        for (int j = low; j <= high - 1; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return (i + 1);
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        quickSort(arr, 0, arr.length - 1);

        System.out.println("Mảng đã sắp xếp:");
        for (int i = 0; i < arr.length; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
}

2.3. Trường Hợp Tốt Nhất và Tệ Nhất

Độ phức tạp thời gian của Quick Sort phụ thuộc vào cách chọn pivot.

• Trường hợp tốt nhất: Pivot được chọn ở giữa mảng. Khi đó, độ phức tạp là O(n log n).
• Trường hợp trung bình: Độ phức tạp vẫn là O(n log n).
• Trường hợp tệ nhất: Pivot luôn là phần tử nhỏ nhất hoặc lớn nhất. Khi đó, độ phức tạp là O(n^2).

Ưu điểm:

• Thường nhanh hơn Merge Sort trong thực tế.
• Không cần thêm không gian bộ nhớ (in-place sorting).

Nhược điểm:

• Độ phức tạp thời gian có thể lên đến O(n^2) trong trường hợp xấu nhất.
• Không ổn định (unstable sorting).

3. So Sánh Merge Sort và Quick Sort

Cả Merge Sort và Quick Sort đều là các thuật toán sắp xếp hiệu quả. Tuy nhiên, chúng có những ưu điểm và nhược điểm riêng. Merge Sort đảm bảo độ phức tạp O(n log n) trong mọi trường hợp, nhưng cần thêm không gian bộ nhớ. Quick Sort thường nhanh hơn trong thực tế, nhưng có thể chậm lại trong trường hợp xấu nhất. Việc lựa chọn thuật toán phù hợp phụ thuộc vào yêu cầu cụ thể của bài toán.

Kết luận

Trong bài viết này, chúng ta đã tìm hiểu về hai thuật toán sắp xếp nâng cao: Merge Sort và Quick Sort. Cả hai đều dựa trên nguyên lý "chia để trị", nhưng có cách tiếp cận khác nhau. Merge Sort ổn định và đảm bảo hiệu suất O(n log n), trong khi Quick Sort thường nhanh hơn nhưng có thể gặp trường hợp xấu nhất O(n^2). Hy vọng bài viết này giúp bạn hiểu rõ hơn về các thuật toán sắp xếp và có thể áp dụng chúng một cách hiệu quả. Hãy tiếp tục khám phá các thuật toán và cấu trúc dữ liệu khác để nâng cao kỹ năng lập trình của bạn!