Sắp xếp nổi bọt
Bách khoa toàn thư mở Wikipedia
Sắp xếp nổi bọt (bubble sort) là một thuật toán sắp xếp đơn giản, so sánh hai phần tử đầu, nếu phần tử đứng trước lớn hơn phần tử đứng sau thì đổi chỗ chúng cho nhau. Tiếp tục làm như vậy với cặp phần tử tiếp theo cho đến cuối tập hợp dữ liệu. Sau đó, quay lại với hai phần tử đầu cho đến khi không còn cần phải đổi chỗ nữa. Nó có tên gọi này từ hình ảnh của các "bọt" khí nhẹ hơn được nổi lên trên. Nó sử dụng phép so sánh các phần tử nên là một sắp xếp kiểu so sánh.
[sửa] Giải thuật
ví dụ:
[sửa] Mã giả
Một đoạn mã giả của thuật toán nổi bọt có thể như sau:
function bubble_sort(list L, number listsize)
loop
has_swapped := 0 //reset flag
for number i from 1 to (listsize - 1)
if L[i] > L[i + 1] //if they are in the wrong order
swap(L[i], L[i + 1]) //exchange them
has_swapped := 1 //we have swapped at least once, list may not be sorted yet
endif
endfor
//if no swaps were made during this pass, the list has been sorted
if has_swapped = 0
exit
endif
endloop
endfunction
