Bài tập Java – Sắp xếp nổi bọt (Bubble Sort) trong Java – VietTuts

Bài tập Java – Sắp xếp nổi bọt (Bubble Sort) trong Java

Đề bài: Viết chương trình Java sắp xếp một dãy số theo thứ tự tăng dần bằng thuật toán nổi bọt (Bubble Sort).

Lời giải

Sắp xếp nổi bọt (Bubble Sort) là một giải thuật sắp xếp đơn giản. Giải thuật sắp xếp này được tiến hành dựa trên việc so sánh cặp phần tử liền kề nhau và tráo đổi thứ tự nếu chúng không theo thứ tự.

Giải thuật này không thích hợp sử dụng với các tập dữ liệu lớn khi mà độ phức tạp trường hợp xấu nhất và trường hợp trung bình là Ο(n2) với n là số phần tử.

Giải thuật sắp xếp nổi bọt là giải thuật chậm nhất trong số các giải thuật sắp xếp cơ bản. Giải thuật này còn chậm hơn giải thuật đổi chỗ trực tiếp mặc dù số lần so sánh bằng nhau, nhưng do đổi chỗ hai phần tử kề nhau nên số lần đổi chỗ nhiều hơn.

Dưới đây là chương trình Java để giải bài sắp xếp nổi bọt (Bubble Sort) trong Java:

package vn.viettuts.array;

public class SapXepNoBot {

    public void bubbleSort(int arr[]) {
        int temp;
        int i, j;

        boolean swapped = false;

        // lap qua tat ca cac so
        for (i = 0; i < arr.length - 1; i++) {
            swapped = false;

            // vong lap thu hai
            for (j = 0; j < arr.length - 1 - i; j++) {
                System.out.print("So sanh cac phan tu: [" + arr[j] + ", " + arr[j + 1] + "]");

                // kiem xa xem so ke tiep co nho hon so hien tai hay khong
                // trao doi cac so.
                // (Muc dich: lam noi bot (bubble) so lon nhat)
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;

                    swapped = true;
                    System.out.println(" => trao doi [" + arr[j] + ", " + arr[j + 1] + "]");
                } else {
                    System.out.println(" => khong can trao doi.");
                }
            }

            // neu khong can trao doi nua, tuc la
            // mang da duoc sap xep va thoat khoi vong lap.
            if (!swapped) {
                break;
            }

            System.out.println("Vong lap thu " + (i + 1));
            display(arr);
        }
    }

    public void display(int arr[]) {
        int i;
        System.out.print("[");

        // Duyet qua tat ca phan tu
        for (i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }

        System.out.print("]\n");
    }

    public static void main(String[] args) {
        // khoi tao mang arr
        int arr[] = { 6, 7, 0, 2, 8, 1, 3, 9, 4, 5 };

        SapXepNoBot sapXepNoBot = new SapXepNoBot();
        System.out.println("Mang du lieu dau vao: ");
        sapXepNoBot.display(arr);
        System.out.println("-----------------------------");
        sapXepNoBot.bubbleSort(arr);
        System.out.println("-----------------------------");
        System.out.println("\nMang sau khi da sap xep: ");
        sapXepNoBot.display(arr);
    }
}

Chạy chương trình Java trên cho kết quả như sau: