Bubble Sort (Sắp xếp nổi bọt) - Thuật toán và ví dụ

Bubble Sort là thuật toán sắp xếp dựa trên so sánh (comparison based). Các phần tử liền kề được so sánh và hoán đổi để tạo thứ tự đúng. Thuật toán đơn giản nhưng không phù hợp tập dữ liệu lớn do chậm.

Độ phức tạp

• Thời gian: Best O(n), Average O(n²), Worst O(n²)
• Không gian: O(1)

Đầu vào / Đầu ra

Input:  56 98 78 12 30 51
Output: 12 30 51 56 78 98

Thuật toán

bubbleSort(array, size)
Begin
    for i = 0 to size-1:
        flag := 0
        for j = 0 to size-i-2:
            if array[j] > array[j+1]:
                swap array[j], array[j+1]
                flag := 1
        if flag != 1: break
    done
End

Ví dụ C++

#include <iostream>
using namespace std;

void swapping(int &a, int &b) { int t=a; a=b; b=t; }
void display(int *arr, int n) { for(int i=0;i arr[j+1]) { swapping(arr[j],arr[j+1]); swaps=1; }
        if(!swaps) break;
    }
}

int main() {
    int n; cout << "Enter number of elements: "; cin >> n;
    int arr[n]; cout << "Enter elements:" << endl;
    for(int i=0;i> arr[i];
    cout << "Array before Sorting: "; display(arr,n);
    bubbleSort(arr,n);
    cout << "Array after Sorting: "; display(arr,n);
}

Kết quả

Enter the number of elements: 6
Enter elements: 56 98 78 12 30 51
Array before Sorting: 56 98 78 12 30 51
Array after Sorting: 12 30 51 56 78 98