Khái niệm
Sắp xếp nổi bọt (bubble sort) so sánh hai phần tử liền kề và đổi chỗ nếu chúng sai thứ tự. Sau mỗi lượt duyệt, phần tử lớn nhất “nổi” lên cuối dãy — giống như bong bóng nổi lên mặt nước.
- Độ phức tạp thời gian: O(n²) — hai vòng lặp lồng nhau
- Độ phức tạp không gian: O(1) — sắp xếp tại chỗ (in-place)
- Ổn định: Có — hai phần tử bằng nhau không đổi chỗ nhau
Bubble sort không hiệu quả với n lớn nhưng rất dễ hiểu và là nền tảng để học các thuật toán sắp xếp khác.
Minh hoạ từng bước
Ví dụ sắp xếp [5, 3, 8, 1, 2]:
Lượt 1: [5,3,8,1,2] → [3,5,8,1,2] → [3,5,8,1,2] → [3,5,1,8,2] → [3,5,1,2,8]
Lượt 2: [3,5,1,2,8] → [3,5,1,2,8] → [3,1,5,2,8] → [3,1,2,5,8]
Lượt 3: [3,1,2,5,8] → [1,3,2,5,8] → [1,2,3,5,8]
Lượt 4: [1,2,3,5,8] → đã xong
Cài đặt cơ bản
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
data = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(data)) # [11, 12, 22, 25, 34, 64, 90]
Cải tiến: Dừng sớm khi đã sắp xếp
Nếu trong một lượt duyệt không có lần đổi chỗ nào, dãy đã sắp xếp xong — có thể dừng sớm.
def bubble_sort_optimized(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped: # Không có đổi chỗ → đã xong
break
return arr
# Dãy gần sắp xếp: chỉ cần 1-2 lượt thay vì n lượt
data = [1, 2, 3, 5, 4] # Chỉ cần 1 lượt
result = bubble_sort_optimized(data)
print(result) # [1, 2, 3, 4, 5]
Bài tập luyện tập
Dễ — Sắp xếp giảm dần
Sửa điều kiện so sánh để sắp xếp theo thứ tự giảm dần.
def bubble_sort_desc(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] < arr[j + 1]: # Đổi điều kiện: < thay vì >
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
data = [3, 1, 4, 1, 5, 9, 2, 6]
print(bubble_sort_desc(data)) # [9, 6, 5, 4, 3, 2, 1, 1]
Trung bình — Đếm số lần đổi chỗ
Đếm tổng số lần đổi chỗ khi sắp xếp một dãy (số lần đổi chỗ = số cặp nghịch thế trong dãy ban đầu).
def dem_doi_cho(arr):
arr = arr[:] # Sao chép để không sửa mảng gốc
n = len(arr)
dem = 0
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
dem += 1
return dem
print(dem_doi_cho([1, 2, 3, 4])) # 0 (đã sắp xếp)
print(dem_doi_cho([4, 3, 2, 1])) # 6 (hoàn toàn ngược)
print(dem_doi_cho([2, 3, 1, 4])) # 2
So sánh với các thuật toán khác
| Thuật toán | Trường hợp tốt nhất | Trường hợp xấu nhất | Ổn định |
|---|---|---|---|
| Bubble Sort | O(n) (có cải tiến) | O(n²) | Có |
| Selection Sort | O(n²) | O(n²) | Không |
| Insertion Sort | O(n) | O(n²) | Có |
| Merge Sort | O(n log n) | O(n log n) | Có |
| Quick Sort | O(n log n) | O(n²) | Không |
Kết luận
Bubble sort là điểm khởi đầu tốt để học về sắp xếp, nhưng không dùng được trong thi đấu khi n > 10⁴. Tiếp theo hãy học Sắp xếp chèn — cũng O(n²) nhưng thực tế nhanh hơn nhiều.
Bình luận