Bài 6.2 - Tự implement bubble sort với Python

Chào mừng bạn đến với bài học thú vị về việc tự tay xây dựng một trong những thuật toán sắp xếp (sorting algorithm) kinh điển và cơ bản nhất: Bubble Sort. Dù không phải là thuật toán hiệu quả nhất cho dữ liệu lớn, Bubble Sort lại là điểm khởi đầu tuyệt vời để bạn hiểu rõ hơn về cách các thuật toán sắp xếp hoạt động và rèn luyện kỹ năng lập trình. Hôm nay, chúng ta sẽ cùng nhau khám phá và implement nó bằng ngôn ngữ Python mạnh mẽ và dễ đọc.

Tại sao lại là Bubble Sort?

Trong thế giới lập trình, việc sắp xếp dữ liệu là một tác vụ cực kỳ phổ biến. Từ việc hiển thị danh sách sản phẩm theo giá, sắp xếp email theo thời gian, hay tổ chức các file trong hệ thống, sắp xếp đóng vai trò quan trọng. Có rất nhiều thuật toán sắp xếp khác nhau, mỗi loại có ưu và nhược điểm riêng.

Bubble Sort nổi bật bởi sự đơn giản của nó. Ý tưởng cốt lõi rất dễ nắm bắt, giống như các "bong bóng" (bubbles) khí lớn hơn nổi lên mặt nước, các phần tử lớn hơn trong danh sách sẽ dần "nổi" lên vị trí cuối cùng của danh sách trong mỗi lần lặp lại.

Ý tưởng cốt lõi của Bubble Sort

Bubble Sort hoạt động dựa trên việc so sánh và hoán đổi (swap) các phần tử kề nhau. Thuật toán sẽ lặp đi lặp lại qua danh sách. Trong mỗi lần lặp (gọi là một pass), nó sẽ so sánh từng cặp phần tử đứng cạnh nhau. Nếu cặp phần tử đó không đúng thứ tự (ví dụ: phần tử bên trái lớn hơn phần tử bên phải khi muốn sắp xếp tăng dần), chúng sẽ được hoán đổi vị trí cho nhau.

Sau mỗi pass, phần tử lớn nhất (hoặc nhỏ nhất, tùy vào thứ tự sắp xếp) trong phần chưa được sắp xếp sẽ "nổi" lên vị trí cuối cùng của phần đó. Điều này có nghĩa là trong các pass tiếp theo, chúng ta không cần phải so sánh lại các phần tử đã ở đúng vị trí cuối cùng.

Hãy hình dung với một ví dụ nhỏ: danh sách [5, 1, 4, 2, 8] cần sắp xếp tăng dần.

Pass 1:
- So sánh 5 và 1: 5 > 1 -> Hoán đổi. Danh sách: [1, 5, 4, 2, 8]
- So sánh 5 và 4: 5 > 4 -> Hoán đổi. Danh sách: [1, 4, 5, 2, 8]
- So sánh 5 và 2: 5 > 2 -> Hoán đổi. Danh sách: [1, 4, 2, 5, 8]
- So sánh 5 và 8: 5 < 8 -> Không hoán đổi. Danh sách: [1, 4, 2, 5, 8]
- Kết thúc Pass 1: Phần tử lớn nhất (8) đã ở vị trí cuối cùng.
Pass 2: (Không cần so sánh đến phần tử cuối cùng là 8 nữa)
- So sánh 1 và 4: 1 < 4 -> Không hoán đổi. Danh sách: [1, 4, 2, 5, 8]
- So sánh 4 và 2: 4 > 2 -> Hoán đổi. Danh sách: [1, 2, 4, 5, 8]
- So sánh 4 và 5: 4 < 5 -> Không hoán đổi. Danh sách: [1, 2, 4, 5, 8]
- Kết thúc Pass 2: Phần tử lớn thứ hai (5) đã ở vị trí áp chót.
Pass 3: (Không cần so sánh đến 5 và 8 nữa)
- So sánh 1 và 2: 1 < 2 -> Không hoán đổi. Danh sách: [1, 2, 4, 5, 8]
- So sánh 2 và 4: 2 < 4 -> Không hoán đổi. Danh sách: [1, 2, 4, 5, 8]
- Kết thúc Pass 3: Phần tử lớn thứ ba (4) đã ở vị trí đúng.
Pass 4: (Chỉ cần so sánh cặp đầu tiên)
- So sánh 1 và 2: 1 < 2 -> Không hoán đổi. Danh sách: [1, 2, 4, 5, 8]
- Kết thúc Pass 4: Danh sách đã được sắp xếp!

Quá trình này lặp lại cho đến khi không còn cặp nào cần hoán đổi trong một pass hoàn chỉnh, hoặc cho đến khi ta chắc chắn rằng tất cả các phần tử đã ở đúng vị trí của chúng.

Implement Bubble Sort với Python

Không gì tuyệt vời hơn là tự tay viết code để hiện thực hóa ý tưởng này. Với Python, việc implement Bubble Sort khá trực quan nhờ cú pháp súc tích và khả năng hoán đổi giá trị dễ dàng.

Đây là mã nguồn Python cho thuật toán Bubble Sort:

def bubble_sort(arr):
    """
    Sắp xếp danh sách 'arr' theo thứ tự tăng dần sử dụng thuật toán Bubble Sort.

    Args:
        arr: Một danh sách (list) các phần tử có thể so sánh được.
    """
    n = len(arr)

    # Lặp qua tất cả các phần tử trong danh sách.
    # Vòng lặp ngoài này xác định số lần 'pass' cần thực hiện.
    # Sau mỗi pass i, i phần tử cuối cùng đã ở đúng vị trí.
    for i in range(n):

        # Cờ hiệu để kiểm tra xem có bất kỳ hoán đổi nào xảy ra trong pass này không.
        # Nếu không có hoán đổi nào, danh sách đã được sắp xếp và chúng ta có thể dừng sớm.
        swapped = False

        # Vòng lặp trong thực hiện việc so sánh và hoán đổi các phần tử kề nhau.
        # Giới hạn j giảm dần vì các phần tử cuối cùng đã được sắp xếp.
        for j in range(0, n-i-1):

            # So sánh phần tử hiện tại (arr[j]) với phần tử kế tiếp (arr[j+1]).
            # Nếu phần tử hiện tại lớn hơn phần tử kế tiếp (để sắp xếp tăng dần)...
            if arr[j] > arr[j+1]:

                # ...thì hoán đổi vị trí của chúng.
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True # Đánh dấu là có hoán đổi xảy ra.

        # Nếu không có bất kỳ hoán đổi nào trong vòng lặp trong (cho pass hiện tại),
        # điều đó có nghĩa là danh sách đã được sắp xếp hoàn toàn.
        # Chúng ta có thể 'break' khỏi vòng lặp ngoài để tối ưu.
        if not swapped:
            break

# --- Các ví dụ minh họa ---

print("--- Ví dụ 1: Danh sách ngẫu nhiên ---")
my_list = [64, 34, 25, 12, 22, 11, 90]
print("Danh sách gốc:", my_list)
bubble_sort(my_list)
print("Danh sách sau khi sắp xếp:", my_list)
print("-" * 20)

print("\n--- Ví dụ 2: Danh sách đã sắp xếp ---")
sorted_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print("Danh sách gốc:", sorted_list)
bubble_sort(sorted_list)
print("Danh sách sau khi sắp xếp:", sorted_list)
print("-" * 20)


print("\n--- Ví dụ 3: Danh sách sắp xếp ngược ---")
reverse_list = [90, 60, 50, 40, 30, 20, 10]
print("Danh sách gốc:", reverse_list)
bubble_sort(reverse_list)
print("Danh sách sau khi sắp xếp:", reverse_list)
print("-" * 20)

print("\n--- Ví dụ 4: Danh sách với các phần tử trùng lặp ---")
duplicate_list = [5, 2, 8, 1, 5, 9, 2, 5]
print("Danh sách gốc:", duplicate_list)
bubble_sort(duplicate_list)
print("Danh sách sau khi sắp xếp:", duplicate_list)
print("-" * 20)

print("\n--- Ví dụ 5: Danh sách rỗng ---")
empty_list = []
print("Danh sách gốc:", empty_list)
bubble_sort(empty_list)
print("Danh sách sau khi sắp xếp:", empty_list)
print("-" * 20)

print("\n--- Ví dụ 6: Danh sách chỉ có một phần tử ---")
single_element_list = [42]
print("Danh sách gốc:", single_element_list)
bubble_sort(single_element_list)
print("Danh sách sau khi sắp xếp:", single_element_list)
print("-" * 20)

Giải thích chi tiết mã nguồn Python

Hãy cùng đi sâu vào từng phần của mã code trên để hiểu rõ hơn cách nó hoạt động:

def bubble_sort(arr)::
- Đây là dòng định nghĩa một hàm (function) có tên là bubble_sort. Hàm này nhận một đối số duy nhất là arr, đại diện cho danh sách (list) mà chúng ta muốn sắp xếp.
- Các dòng chú thích (docstring) bên dưới giải thích mục đích của hàm và đối số của nó. Đây là một thói quen tốt trong lập trình để mã dễ hiểu hơn.
n = len(arr):
- Chúng ta lấy độ dài của danh sách arr và gán vào biến n. Điều này giúp chúng ta biết cần thực hiện bao nhiêu lần lặp và xác định các chỉ số (index) trong danh sách.
for i in range(n)::
- Đây là vòng lặp ngoài. Nó chạy từ i = 0 đến n-1.
- Mỗi lần lặp của vòng lặp ngoài tương ứng với một "pass" của Bubble Sort.
- Tại sao lại là n lần? Về lý thuyết, chúng ta chỉ cần n-1 pass để đảm bảo danh sách có n phần tử được sắp xếp. Tuy nhiên, việc lặp đủ n lần (hoặc n-1 lần tùy cách viết) vẫn đảm bảo thuật toán chạy đúng. Trong cài đặt này, vòng lặp range(n) chạy n lần. Sau pass thứ i, phần tử lớn nhất trong n-i phần tử chưa được sắp xếp sẽ được đưa về đúng vị trí.
swapped = False:
- Biến swapped được khởi tạo là False ở đầu mỗi vòng lặp ngoài (mỗi pass).
- Đây là một kỹ thuật tối ưu hóa quan trọng. Nếu trong suốt một pass hoàn chỉnh của vòng lặp trong mà không có bất kỳ cặp nào được hoán đổi (swapped vẫn giữ nguyên là False), điều đó chứng tỏ rằng danh sách đã hoàn toàn được sắp xếp và chúng ta không cần thực hiện thêm các pass nữa.
for j in range(0, n-i-1)::
- Đây là vòng lặp trong. Nó thực hiện việc so sánh và hoán đổi các phần tử kề nhau trong pass hiện tại.
- j là chỉ số của phần tử đầu tiên trong cặp đang được so sánh (arr[j] và arr[j+1]).
- Vòng lặp chạy từ j = 0 đến n-i-2.
- Tại sao lại là n-i-1?
  - n-1: Là chỉ số cuối cùng có thể có trong danh sách.
  - n-i-1: Sau i pass của vòng lặp ngoài, i phần tử cuối cùng của danh sách đã được sắp xếp đúng vị trí. Chúng ta không cần so sánh đến những phần tử này nữa. Do đó, giới hạn trên của j là (n-1) - i - 1 + 1 = n-i-1. Vòng lặp trong chỉ cần đi đến phần tử trước phần tử đầu tiên đã được sắp xếp ở cuối danh sách. Tức là j sẽ chạy đến n-i-2, so sánh arr[n-i-2] với arr[n-i-1].
if arr[j] > arr[j+1]::
- Đây là điều kiện để kiểm tra xem cặp phần tử kề nhau arr[j] và arr[j+1] có đúng thứ tự hay không (để sắp xếp tăng dần, arr[j] phải nhỏ hơn hoặc bằng arr[j+1]).
- Nếu arr[j] lớn hơn arr[j+1], chúng cần được hoán đổi.
arr[j], arr[j+1] = arr[j+1], arr[j]:
- Đây là cách hoán đổi giá trị cực kỳ Pythonic. Nó sử dụng tính năng gán đồng thời của Python.
- Biểu thức bên phải (arr[j+1], arr[j]) tạo ra một tuple chứa giá trị của arr[j+1] và arr[j] trước khi hoán đổi.
- Biểu thức bên trái (arr[j], arr[j+1]) gán các giá trị trong tuple đó vào arr[j] và arr[j+1] theo thứ tự mới. Kết quả là giá trị của hai phần tử được đổi chỗ cho nhau một cách hiệu quả chỉ trong một dòng code.
- swapped = True: Nếu việc hoán đổi xảy ra, chúng ta đặt cờ swapped thành True để ghi nhận.
if not swapped: break:
- Sau khi vòng lặp trong kết thúc một pass (for j...), chúng ta kiểm tra cờ swapped.
- Nếu swapped vẫn là False (có nghĩa là không có bất kỳ hoán đổi nào diễn ra trong pass đó), danh sách chắc chắn đã được sắp xếp.
- Câu lệnh break sẽ thoát khỏi vòng lặp ngoài (for i...) ngay lập tức, giúp thuật toán dừng sớm khi cần thiết, tránh các pass không cần thiết. Đây là một tối ưu nhỏ nhưng hiệu quả, đặc biệt với các danh sách đã gần được sắp xếp.

Hàm bubble_sort thực hiện sắp xếp tại chỗ (in-place), nghĩa là nó thay đổi trực tiếp danh sách được truyền vào chứ không trả về một danh sách mới.

Khám phá các ví dụ minh họa

Phần cuối của mã code là các ví dụ thực tế sử dụng hàm bubble_sort với nhiều loại danh sách khác nhau:

Ví dụ 1: Danh sách ngẫu nhiên: Thử nghiệm với một danh sách chứa các số không theo thứ tự cụ thể. Kết quả là một danh sách được sắp xếp tăng dần chính xác.
Ví dụ 2: Danh sách đã sắp xếp: Cho thấy thuật toán vẫn chạy các pass, nhưng nhờ có phần tối ưu if not swapped: break, nó sẽ dừng lại sau pass đầu tiên (vì không có hoán đổi nào xảy ra), chứng minh tính hiệu quả của việc dừng sớm.
Ví dụ 3: Danh sách sắp xếp ngược: Đây là trường hợp "xấu nhất" (worst-case) cho Bubble Sort, khi mỗi cặp phần tử đều cần hoán đổi. Thuật toán sẽ thực hiện số lượng hoán đổi và so sánh tối đa.
Ví dụ 4: Danh sách với các phần tử trùng lặp: Minh họa rằng Bubble Sort xử lý đúng đắn các trường hợp có giá trị trùng lặp, duy trì thứ tự tương đối của các phần tử bằng nhau (nếu cần, mặc dù Bubble Sort gốc không đảm bảo tính ổn định nếu không có tùy chỉnh). Với các số đơn giản, điều này không rõ ràng lắm, nhưng thuật toán vẫn hoạt động.
Ví dụ 5: Danh sách rỗng: Thử nghiệm với trường hợp cạnh (edge case) là một danh sách không có phần tử nào. Code chạy mà không gặp lỗi và trả về danh sách rỗng.
Ví dụ 6: Danh sách chỉ có một phần tử: Một trường hợp cạnh khác. Code cũng chạy đúng và trả về danh sách nguyên vẹn.

Các ví dụ này giúp bạn thấy được cách hàm bubble_sort hoạt động trong các kịch bản khác nhau và xác nhận rằng nó đang sắp xếp đúng như mong đợi.

Hiệu quả của Bubble Sort (Độ phức tạp)

Mặc dù đơn giản, Bubble Sort không phải là thuật toán hiệu quả cho các tập dữ liệu lớn.

Độ phức tạp thời gian (Time Complexity): Trong trường hợp xấu nhất và trung bình, Bubble Sort có độ phức tạp thời gian là O(n^2), trong đó n là số lượng phần tử trong danh sách. Điều này có nghĩa là khi số lượng phần tử tăng lên gấp đôi, thời gian chạy có thể tăng lên gấp bốn lần. Vòng lặp lồng nhau (for i và for j) chính là nguyên nhân dẫn đến độ phức tạp bậc hai này. Ngay cả trong trường hợp tốt nhất (danh sách đã được sắp xếp), nếu không có tối ưu hóa dừng sớm, nó vẫn có thể chạy gần như O(n^2) phép so sánh. Với tối ưu hóa dừng sớm, trường hợp tốt nhất là O(n) (cần duyệt qua danh sách một lần để xác định không có hoán đổi).
Độ phức tạp không gian (Space Complexity): Bubble Sort có độ phức tạp không gian là O(1). Điều này có nghĩa là nó chỉ sử dụng một lượng bộ nhớ cố định (cho các biến như n, i, j, swapped, và không gian cho việc hoán đổi) bất kể kích thước của danh sách. Nó thực hiện sắp xếp "tại chỗ".

Do độ phức tạp O(n^2), Bubble Sort thường chỉ được sử dụng trong các bài giảng giới thiệu về thuật toán sắp xếp hoặc khi làm việc với các danh sách rất nhỏ. Đối với các ứng dụng thực tế, các thuật toán hiệu quả hơn như Merge Sort, Quick Sort, hay Timsort (được sử dụng trong Python) là lựa chọn ưu tiên.

Tóm tắt lại

Chúng ta đã cùng nhau đi qua hành trình tìm hiểu và tự tay cài đặt Bubble Sort bằng Python. Bạn đã nắm được:

Ý tưởng cơ bản: So sánh và hoán đổi các phần tử kề nhau.
Cách thức hoạt động theo từng pass.
Mã nguồn Python đầy đủ cho thuật toán.
Giải thích chi tiết từng dòng code, bao gồm cả tối ưu hóa dừng sớm.
Xem các ví dụ minh họa với nhiều loại danh sách khác nhau.
Hiểu về độ phức tạp thời gian O(n^2) và độ phức tạp không gian O(1) của thuật toán.

Việc tự mình implement thuật toán này giúp củng cố kiến thức về vòng lặp, điều kiện, và thao tác trên danh sách trong Python, đồng thời là bước đệm quan trọng để bạn khám phá các thuật toán sắp xếp phức tạp và hiệu quả hơn trong tương lai.

Hãy thử chạy đoạn code trên máy tính của bạn, thay đổi các ví dụ đầu vào và quan sát kết quả nhé! Chúc bạn học tốt!

Comments

There are no comments at the moment.