Thuật toán sắp xếp nổi bọt (Bubble Sort) trong java

Thuật toán sắp xếp nổi bọt (Bubble Sort) là một trong những thuật toán sắp xếp đơn giản và được sử dụng phổ biến trong lập trình. Nó hoạt động bằng cách so sánh các cặp phần tử liên tiếp trong mảng và hoán đổi chúng nếu chúng không ở đúng thứ tự. Quá trình này lặp lại cho đến khi không còn cặp phần tử nào cần hoán đổi nữa.

Dưới đây là code Java cho thuật toán sắp xếp nổi bọt:

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]) {
                // hoán đổi arr[j] và arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
}

Trong đó, arr là mảng cần sắp xếp. Hàm bubbleSort sử dụng hai vòng lặp lồng nhau để so sánh các phần tử của mảng và hoán đổi chúng nếu cần thiết. Vòng lặp ngoài cùng chạy từ đầu đến cuối mảng, trong khi vòng lặp bên trong chạy từ đầu đến cuối mảng trừ đi số lần lặp của vòng lặp ngoài cùng.

Khi một cặp phần tử cần hoán đổi, ta sử dụng biến tạm temp để lưu trữ giá trị của phần tử đầu tiên trước khi hoán đổi. Sau đó, ta gán giá trị của phần tử thứ hai cho phần tử đầu tiên và giá trị của biến tạm cho phần tử thứ hai. Quá trình này được lặp lại cho đến khi không còn cặp phần tử nào cần hoán đổi.

Thuật toán sắp xếp nổi bọt có độ phức tạp thời gian O(n^2), với n là số lượng phần tử trong mảng. Do đó, nó không hiệu quả khi sử dụng cho các mảng lớn. Tuy nhiên, với các mảng có số lượng phần tử nhỏ hoặc đã gần được sắp xếp trước đó, thuật toán này có thể hoạt động tốt.

Dưới đây là một ví dụ về thuật toán sắp xếp nổi bọt trong Java để sắp xếp một mảng các số nguyên theo thứ tự tăng dần:

public class BubbleSortExample {
    public static void main(String[] args) {
        int[] arr = { 5, 3, 1, 9, 8 };

        System.out.println("Mảng chưa sắp xếp: " + Arrays.toString(arr));

        // sắp xếp mảng
        bubbleSort(arr);

        System.out.println("Mảng đã sắp xếp: " + Arrays.toString(arr));
    }

    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        int temp = 0;

        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                // so sánh hai phần tử liền kề
                if (arr[j] > arr[j + 1]) {
                    // hoán đổi hai phần tử
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}