Giải thuật sắp xếp cơ bản: Bubble Sort, Insertion Sort, Selection Sort

Chào mừng bạn đến với bài viết thứ 11 trong series về cấu trúc dữ liệu và giải thuật. Hôm nay, chúng ta sẽ cùng nhau khám phá các giải thuật sắp xếp cơ bản. Cụ thể là Bubble Sort (Sắp xếp nổi bọt), Insertion Sort (Sắp xếp chèn) và Selection Sort (Sắp xếp chọn). Chúng ta sẽ tìm hiểu cách chúng hoạt động, ưu nhược điểm và độ phức tạp của từng giải thuật. Ví dụ minh họa sẽ được viết bằng ngôn ngữ Java.

1. Giới thiệu về sắp xếp

Sắp xếp là một trong những thao tác quan trọng nhất trong khoa học máy tính. Nó giúp chúng ta tổ chức dữ liệu một cách có trật tự. Từ đó, việc tìm kiếm và xử lý dữ liệu trở nên dễ dàng và hiệu quả hơn. Có rất nhiều giải thuật sắp xếp khác nhau. Mỗi giải thuật có những ưu điểm và nhược điểm riêng. Việc lựa chọn giải thuật phù hợp phụ thuộc vào đặc điểm của dữ liệu và yêu cầu của bài toán.

2. Sắp xếp nổi bọt (Bubble Sort)

Bubble Sort là một trong những giải thuật sắp xếp đơn giản nhất. Nó hoạt động bằng cách so sánh các cặp phần tử liền kề. Nếu chúng không đúng thứ tự, chúng sẽ được hoán đổi. Quá trình này lặp đi lặp lại cho đến khi toàn bộ mảng được sắp xếp. Các phần tử lớn hơn sẽ "nổi" lên trên giống như bong bóng.

Ví dụ (Java):

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Swap arr[j] and arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr);
        System.out.println("Sorted array:");
        for (int i = 0; i < arr.length; ++i)
            System.out.print(arr[i] + " ");
    }
}

Độ phức tạp thời gian:

• Trường hợp tốt nhất: O(n) - Khi mảng đã được sắp xếp.
• Trường hợp trung bình: O(n^2)
• Trường hợp xấu nhất: O(n^2) - Khi mảng được sắp xếp ngược lại.

Độ phức tạp không gian: O(1) - Bubble Sort là một giải thuật tại chỗ (in-place), không cần thêm không gian lưu trữ đáng kể.

3. Sắp xếp chèn (Insertion Sort)

Insertion Sort hoạt động bằng cách chia mảng thành hai phần: đã sắp xếp và chưa sắp xếp. Ở mỗi bước, nó lấy một phần tử từ phần chưa sắp xếp và chèn nó vào đúng vị trí trong phần đã sắp xếp. Giống như cách bạn sắp xếp bài khi chơi bài.

Ví dụ (Java):

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; ++i) {
            int key = arr[i];
            int j = i - 1;

            /* Move elements of arr[0..i-1], that are
               greater than key, to one position ahead
               of their current position */
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        insertionSort(arr);
        System.out.println("Sorted array:");
        for (int i = 0; i < arr.length; ++i)
            System.out.print(arr[i] + " ");
    }
}

Độ phức tạp thời gian:

• Trường hợp tốt nhất: O(n) - Khi mảng đã được sắp xếp.
• Trường hợp trung bình: O(n^2)
• Trường hợp xấu nhất: O(n^2) - Khi mảng được sắp xếp ngược lại.

Độ phức tạp không gian: O(1) - Insertion Sort cũng là một giải thuật tại chỗ.

4. Sắp xếp chọn (Selection Sort)

Selection Sort hoạt động bằng cách tìm phần tử nhỏ nhất (hoặc lớn nhất) trong mảng chưa sắp xếp. Sau đó, nó hoán đổi phần tử này với phần tử đầu tiên của mảng chưa sắp xếp. Quá trình này lặp đi lặp lại cho đến khi toàn bộ mảng được sắp xếp.

Ví dụ (Java):

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;

        for (int i = 0; i < n - 1; i++) {
            int min_idx = i;
            for (int j = i + 1; j < n; j++)
                if (arr[j] < arr[min_idx])
                    min_idx = j;

            // Swap the found minimum element with the first
            // element
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("Sorted array:");
        for (int i = 0; i < arr.length; ++i)
            System.out.print(arr[i] + " ");
    }
}

Độ phức tạp thời gian:

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

Độ phức tạp không gian: O(1) - Selection Sort cũng là một giải thuật tại chỗ.

5. So sánh các giải thuật

Cả ba giải thuật này (Bubble Sort, Insertion Sort và Selection Sort) đều có độ phức tạp thời gian O(n^2) trong trường hợp trung bình và xấu nhất. Điều này có nghĩa là chúng không hiệu quả đối với các mảng lớn. Tuy nhiên, chúng rất dễ hiểu và dễ cài đặt. Insertion Sort thường nhanh hơn Bubble Sort và Selection Sort trong thực tế, đặc biệt là với dữ liệu gần như đã được sắp xếp.

6. Khi nào nên sử dụng?

Các giải thuật sắp xếp cơ bản này thường được sử dụng cho mục đích giáo dục hoặc với các mảng nhỏ. Trong thực tế, các giải thuật sắp xếp phức tạp hơn như Merge Sort, Quick Sort hoặc Heap Sort thường được ưu tiên hơn vì chúng có độ phức tạp thời gian tốt hơn (O(n log n)). Tuy nhiên, việc hiểu rõ các giải thuật cơ bản là nền tảng quan trọng để nắm vững các giải thuật phức tạp hơn.

7. Tổng kết

Trong bài viết này, chúng ta đã tìm hiểu về ba giải thuật sắp xếp cơ bản: Bubble Sort, Insertion Sort và Selection Sort. Chúng ta đã phân tích cách chúng hoạt động, độ phức tạp thời gian và không gian của từng giải thuật. Hy vọng bài viết này đã cung cấp cho bạn những kiến thức hữu ích. Hãy tiếp tục theo dõi series để khám phá thêm nhiều cấu trúc dữ liệu và giải thuật thú vị khác nhé!