Giải thuật
Ý tưởng chính của giải thuật là xuất phát từ cuối (đầu) dãy, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ (lớn) hơn trong cặp phần tử đó về vị trí đúng đầu (cuối) dãy hiện hành, sau đó sẽ không xét đến nó ở bước tiếp theo, do vậy ở lần xử lý thứ i sẽ có vị trí đầu dãy là i . Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét. Các bước tiến hành như sau :
- Bước 1 : i = 1; // lần xử lý đầu tiên
- Bước 2 : j = N; //Duyệt từ cuối dãy ngược về vị trí i
Trong khi (j >i) thực hiện:
Nếu a[j]<a[j-1]: hoán vị a[j] và a[j-1];//xét cặp phần tử kế cận
j = j-1;
- Bước 3 : i = i+1; // lần xử lý kế tiếp
Nếu i >N-1: Hết dãy. Dừng
Ngược lại : Lặp lại Bước 2.
-
Ví dụ
Cho dãy số a: 12 2 8 5 1 6 4 15
*Cài đặt
Cài đặt thuật toán sắp xếp theo kiểu nổi bọt thành hàm BubbleSort:
Pascal:
void BubbleSort(int a[],int n)
{
int i,j;
for(i=0;i<n-1;i++)
for(j=n-1;j>i;j–)
if(a[j]<a[j-1])
HoanVi(a[j],a[j-1])
}
*Ðánh giá giải thuật
Ðối với giải thuật nổi bọt, số lượng các phép so sánh xảy ra không phụ thuộc vào tình trạng của dãy số ban đầu, nhưng số lượng phép hoán vị thực hiện tùy thuộc vào kết qủa so sánh, có thể ước lược trong từng trường hợp như sau :
| Trường hợp | Số lần so sánh | Số lần hoán vị |
| Tốt nhất |  |
0 |
| Xấu nhất |  |
 |
Nhận xét
@ BubbleSort có các khuyết điểm sau: không nhận diện được tình trạng dãy đã có thứ tự hay có thứ tự từng phần. Các phần tử nhỏ được đưa về vị trí đúng rất nhanh, trong khi các phần tử lớn lại được đưa về vị trí đúng rất chậm
