Giới Thiệu

Thuật toán Sắp xếp Sủi Bọt (Bubble Sort) là một trong những thuật toán sắp xếp cơ bản và đơn giản. Đây là thuật toán rất dễ hiểu và dễ triển khai, thường được sử dụng như một ví dụ giảng dạy cho những người mới bắt đầu học về các thuật toán sắp xếp. Mặc dù thuật toán này không phải là lựa chọn tối ưu cho các mảng lớn, nó vẫn có ứng dụng trong các tình huống cụ thể.

Ý Tưởng

Thuật toán Sắp xếp Sủi Bọt hoạt động bằng cách lặp đi lặp lại qua mảng, so sánh từng cặp phần tử kề nhau và hoán đổi chúng nếu chúng không theo thứ tự mong muốn. Mỗi lần lặp qua mảng, phần tử lớn nhất sẽ “nổi lên” vị trí cuối cùng của mảng, giống như bọt khí nổi lên trên mặt nước. Quá trình này tiếp tục cho đến khi không còn phần tử nào cần phải hoán đổi, tức là 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 Sủi Bọt được triển khai bằng Java:

public class BubbleSortExample {
    // Phương thức để thực hiện sắp xếp sủi bọt
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;

        // Lặp qua mảng nhiều lần cho đến khi không còn phần tử nào cần hoán đổi
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            // So sánh và hoán đổi các phần tử kề nhau
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Hoán đổi arr[j] và arr[j + 1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            // Nếu không có phần tử nào bị hoán đổi, mảng đã được sắp xếp
            if (!swapped) break;
        }
    }

    // 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);

        bubbleSort(array);

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

Đánh Giá Thuật Toán Sắp Xếp Sủi Bọt

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

• Trường hợp tốt: O(n) (Khi mảng đã được sắp xếp sẵn và thuật toán phát hiện rằng không có phần tử nào bị hoán đổi trong lượt lặp cuối cùng)
• Trung bình: O(n²)
• Trường hợp xấu: O(n²) (Khi mảng bị sắp xếp ngược hoàn toàn)

Không gian bộ nhớ sử dụng: O(1)

Tại chỗ (In-place): Có

Cách sử dụng:

Sắp xếp sủi bọt thường được áp dụng trong các tình huống sau:

• Dữ liệu đầu vào nhỏ: Khi làm việc với các mảng nhỏ, thuật toán này có thể là một lựa chọn hợp lý.
• Dễ triển khai và hiểu: Khi cần một thuật toán đơn giản để giải thích hoặc triển khai nhanh chóng.
• Yêu cầu tính dễ kiểm tra: Khi việc kiểm tra và xác nhận tính đúng đắn của thuật toán là quan trọng, sắp xếp sủi bọt có thể cung cấp một cách tiếp cận đơn giản.

Mặc dù thuật toán sắp xếp sủi bọt có thể không phải là lựa chọn tốt nhất cho các mảng lớn do độ phức tạp thời gian O(n²), nó vẫn hữu ích trong các trường hợp học tập và các tình huống cụ thể với dữ liệu nhỏ.