Bubble Sort - Deft Blog

Bubble sort là thuật toán hoạt động bằng cách hoán đổi vị trí hai phần tử tử liền kề nhau nếu chúng sai vị trí.

B1: Khởi tạo i = 0
B2: Loop i từ 0 đến N - 2, 
   + Khởi tạo j = i + 1
   + Loop j từ i + 1 đến N - 1
     $ Nếu arr[j] > arr[j + 1] swap arr[j] và arr[j + 1]

Sau mỗi lần lặp của biến i: mảng arr[] có độ dài bằng size

Nếu sắp xếp tăng dần: đưa giá trị lớn nhất về vị trí size – i
Nếu sắp xếp giảm dần: đưa giá trị nhỏ nhất về vị trí size – i

Lưu ý: giá trị của biến i cũng chính là số lượng phần tử đã được sắp xếp trong mảng.

Implementation

public static <T extends Comparable<T>> void sort(T[] arr, int n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                /*
                 * Use codition arr[j] with a[j + 1]
                 * Sort by ASC => Compare ">"
                 * Sort by DESC => Compare "<"
                 */

                if (arr[j].compareTo(arr[j + 1]) < 0) {
                    T tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
        }
    }

Bubble sort có độ phức tạp θ(n²) với mọi tập dữ liệu.

Tối ưu thuật toán: Ta thấy với mỗi lần lặp, bubble sort liên tục hoán đổi nếu vị trí của 2 phần tử liền kề không đúng thứ tự. Vậy nếu ở một lần lặp nào đó mà không có sự hoán đổi thì có nghĩa là không có bất kỳ cặp số liền kề nào đứng sai vị trí => ta dừng phép sắp xếp.

Minh hoạ sắp xếp tăng dần:

arr[] = {7, 6, 8, 4, 3, 0}

Lần lặp 1:

{7, 6, 8, 4, 3, 0} => {6, 7, 8, 4, 3, 0}
{6, 7, 8, 4, 3, 0} => {6, 7, 8, 4, 3, 0}
{6, 7, 8, 4, 3, 0} => {6, 7, 4, 8, 3, 0}
{6, 7, 4, 8, 3, 0} => {6, 7, 4, 3, 8, 0}
{6, 7, 4, 3, 8, 0} => {6, 7, 4, 3, 0, 8}

Lần lặp 2:

{6, 7, 4, 3, 0, 8} => {6, 7, 4, 3, 0, 8}
{6, 7, 4, 3, 0, 8} => {6, 4, 7, 3, 0, 8}
{6, 4, 7, 3, 0, 8} => {6, 4, 3, 7, 0, 8}
{6, 4, 3, 7, 0, 8} => {6, 4, 3, 0, 7, 8}

Lần lặp 3:

{6, 4, 3, 0, 7, 8} => {4, 6, 3, 0, 7, 8}
{4, 6, 3, 0, 7, 8} => {4, 3, 6, 0, 7, 8}
{4, 3, 6, 0, 7, 8} => {4, 3, 0, 6, 7, 8}

Lần lặp 4:

{4, 3, 0, 6, 7, 8} => {3, 4, 0, 6, 7, 8}
{3, 4, 0, 6, 7, 8} => {3, 0, 4, 6, 7, 8}

Lần lặp 5:

{3, 0, 4, 6, 7, 8} => {0, 3, 4, 6, 7, 8}

Link source code: bubble sort