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

1. Bài toán
Cho dãy X = {X1, X1, ..., Xn}, hãy sắp xếp dãy theo chiều không giảm.

2. Ý tưởng
- Thao tác cơ bản của thuật toán này là so sánh hai phần từ kề nhau X[i] và X[i-1], nếu chúng đứng chưa đúng thứ tự thì đổi chổ cho nhau. Sau một chu trình so sánh, nếu thực hiện từ phải sang trái phần từ đầu tiên (hoặc cuối cùng nếu theo chiều ngược lại) đứng đúng vị trí, bỏ qua phần từ đó.
- Tiếp tục thực hiện với dãy là những phần tử còn lại.

3. Giải thuật
- Bước 1: i=1
- Bước 2: Lần lượt so sánh và đổi chổ (nếu cần) từ phải sang trái đối với các phần từ từ X[n] đến X[i]
- Bước 3: i=i+1
- Bước 4:
* Nếu i < n, quay lại Bước 2.
* Ngược lại, dừng, dãy đã cho đã sắp xếp đúng vị trí.

4. Mã thực thi (tựa C)

Code:


void BubbleSort(int X[], int n)
{
   int i, j;
   for (i=1, i<n, i++)
      for (j=n, j>i, j--)
         if (X[j]<X[j-1])
            swap(X[j-1],X[j]);
}
void swap (int x, int y)
{
   int temp;
   temp=x;
   x=y;
   y=temp;
}


5. Ví dụ
X = {7, 2, 5, 4, 1, 3, 8, 6}
Dãy ban đầu: 7, 2, 5, 4, 1, 3, 8, 6
i=1, j=8, swap(X[j-1],X[j], ta có 7, 2, 5, 4, 1, 3, 6, 8
i=1, j=7, không đổi chổ, ta có 7, 2, 5, 4, 1, 3, 6, 8
i=1, j=6, không đổi chổ, ta có 7, 2, 5, 4, 1, 3, 6, 8
i=1, j=5, swap(X[j-1],X[j], ta có 7, 2, 5, 1, 4, 3, 6, 8
i=1, j=4, swap(X[j-1],X[j], ta có 7, 2, 1, 5, 4, 3, 6, 8
i=1, j=3, swap(X[j-1],X[j], ta có 7, 1, 2, 5, 4, 3, 6, 8
i=1, j=2, swap(X[j-1],X[j], ta có 1, 7, 2, 5, 4, 3, 6, 8

i=2, thực hiện tương tự ta có 1, 2, 7, 3, 5, 4, 6, 8
i=3, thực hiện tương tự ta có 1, 2, 3, 7, 4, 5, 6, 8
i=4, thực hiện tương tự ta có 1, 2, 3, 4, 7, 5, 6, 8
i=5, thực hiện tương tự ta có 1, 2, 3, 4, 5, 7, 6, 8
i=6, thực hiện tương tự ta có 1, 2, 3, 4, 5, 6, 7, 8
i=7, thực hiện tương tự ta có 1, 2, 3, 4, 5, 6, 7, 8

Cuối cùng ta có 1, 2, 3, 4, 5, 6, 7, 8, dãy đã được sắp xếp.

Mình thấy có một code C# tương tự cũng dành cho thuật toán nổi bọt xin đóng góp

Code:

void BubbleSort(int ar[]) 
{
    int n,temp,i,j;
  n=ar.Length;
  bool doicho = true;
  for(i = 1; i < n && doicho == true; i++)
  {
    doicho = false;
      for(j = 0;j < n-i; j++)
            if(nodes[j] < nodes[j+1])
        {
            doicho = true;
            temp = nodes[j];
            nodes[j] = nodes[j+1];
            nodes[j+1] = temp;
        }
  }
}

Nguồn: Thuật toán bubble sort

Độ phức tạp của thuật toán nổi bọt:
Hiệu suất:
- Độ phức tạp: O(n^2)
- Đây là thuật toán kém nhất