Sắp xếp nổi bọt hay bubble sort là thuật toán sắp xếp đầu tiên mà mình giới thiệu đến các bạn và cũng là thuật toán đơn giản nhất trong các thuật toán mà mình sẽ giới thiệu, ý tưởng của thuật toán này như sau:

Duyệt qua danh sách, làm cho các phần tử lớn nhất hoặc nhỏ nhất dịch chuyển về phía cuối danh sách, tiếp tục lại làm phần tử lớn nhất hoặc nhỏ nhất kế đó dịch chuyển về cuối hay chính là làm cho phần tử nhỏ nhất (hoặc lớn nhất) nổi lên, cứ như vậy cho đến hết danh sách Cụ thể các bước thực hiện của giải thuật này như sau:

  1. Gán i = 0
  2. Gán j = 0
  3. Nếu A[j] > A[j + 1] thì đối chỗ A[j] và A[j + 1]
  4. Nếu j < n – i – 1:
    • Đúng thì j = j + 1 và quay lại bước 3
    • Sai thì sang bước 5
  5. Nếu i < n – 1:
    • Đúng thì i = i + 1 và quay lại bước 2
    • Sai thì dừng lại

Thật đơn giản đúng không nào, chúng ta hãy cùng cài đặt thuật toán này trong C++ nha.

void BubbleSort(int A[], int n)
{
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - i - 1; j++)
            if (A[j] > A[j + 1])
                swap(A[j], A[j + 1]); // đổi chỗ A[j] và A[j + 1]
}

Sắp xếp nổi bọt là một thuật toán sắp xếp ổn định. Về độ phức tạp, do dùng hai vòng lặp lồng vào nhau nên độ phức tạp thời gian trung bình của thuật toán này là O(n2).

Nguồn: https://topdev.vn/blog/thuat-toan-sap-xep-trong-c/