Bài 6.3 - Thuật toán Sắp xếp Chọn (Selection Sort) với Python

Chào mừng bạn quay trở lại với hành trình khám phá các thuật toán sắp xếp! Trong bài học này, chúng ta sẽ đi sâu vào một trong những thuật toán sắp xếp đơn giản và dễ hiểu nhất: Sắp xếp Chọn (Selection Sort). Mặc dù không phải là thuật toán hiệu quả nhất cho các tập dữ liệu lớn, Selection Sort mang đến một cách tiếp cận rất trực quan và là bước đệm tuyệt vời để hiểu các thuật toán phức tạp hơn. Chúng ta sẽ cùng nhau tìm hiểu cách nó hoạt động và cách cài đặt nó bằng Python.

Selection Sort Hoạt Động Như Thế Nào?

Ý tưởng cốt lõi của Selection Sort rất đơn giản, giống như bạn đang sắp xếp một bộ bài vậy. Nó chia danh sách (hay mảng) thành hai phần: một phần đã được sắp xếp ở bên trái và một phần chưa được sắp xếp ở bên phải. Ban đầu, phần đã sắp xếp là trống, và toàn bộ danh sách là phần chưa được sắp xếp.

Thuật toán hoạt động bằng cách lặp đi lặp lại các bước sau:

Tìm phần tử nhỏ nhất (hoặc lớn nhất, tùy thuộc vào thứ tự sắp xếp tăng dần hay giảm dần) trong phần chưa được sắp xếp.
Hoán đổi (swap) phần tử nhỏ nhất đó với phần tử đầu tiên của phần chưa được sắp xếp.
Mở rộng phần đã được sắp xếp sang phải thêm một vị trí, và thu nhỏ phần chưa được sắp xếp lại tương ứng.
Lặp lại quá trình này cho đến khi toàn bộ danh sách được sắp xếp.

Nghe có vẻ đơn giản phải không? Hãy hình dung nó như việc bạn đi "chọn" (select) phần tử nhỏ nhất ở phần còn lại và đặt nó vào đúng vị trí của nó ở đầu danh sách chưa sắp xếp.

Minh Họa Các Bước Chạy Của Selection Sort

Hãy cùng minh họa cách Selection Sort hoạt động với một ví dụ cụ thể. Giả sử chúng ta có danh sách [64, 25, 12, 22, 11] cần sắp xếp tăng dần.

Danh sách ban đầu: [64, 25, 12, 22, 11]
- Phần đã sắp xếp: []
- Phần chưa sắp xếp: [64, 25, 12, 22, 11]
Lượt 1:
- Tìm phần tử nhỏ nhất trong [64, 25, 12, 22, 11]. Phần tử nhỏ nhất là 11.
- Hoán đổi 11 với phần tử đầu tiên của phần chưa sắp xếp (64).
- Danh sách trở thành: [11, 25, 12, 22, 64]
- Phần đã sắp xếp: [11]
- Phần chưa sắp xếp: [25, 12, 22, 64]
Lượt 2:
- Tìm phần tử nhỏ nhất trong phần chưa sắp xếp [25, 12, 22, 64]. Phần tử nhỏ nhất là 12.
- Hoán đổi 12 với phần tử đầu tiên của phần chưa sắp xếp (25).
- Danh sách trở thành: [11, 12, 25, 22, 64]
- Phần đã sắp xếp: [11, 12]
- Phần chưa sắp xếp: [25, 22, 64]
Lượt 3:
- Tìm phần tử nhỏ nhất trong phần chưa sắp xếp [25, 22, 64]. Phần tử nhỏ nhất là 22.
- Hoán đổi 22 với phần tử đầu tiên của phần chưa sắp xếp (25).
- Danh sách trở thành: [11, 12, 22, 25, 64]
- Phần đã sắp xếp: [11, 12, 22]
- Phần chưa sắp xếp: [25, 64]
Lượt 4:
- Tìm phần tử nhỏ nhất trong phần chưa sắp xếp [25, 64]. Phần tử nhỏ nhất là 25.
- Hoán đổi 25 với phần tử đầu tiên của phần chưa sắp xếp (25).
- Danh sách trở thành: [11, 12, 22, 25, 64]
- Phần đã sắp xếp: [11, 12, 22, 25]
- Phần chưa sắp xếp: [64]
Chỉ còn lại một phần tử trong phần chưa sắp xếp, nó đương nhiên đã ở đúng vị trí. Danh sách đã được sắp xếp hoàn toàn!

Cài Đặt Selection Sort Bằng Python

Bây giờ, chúng ta sẽ chuyển ý tưởng này thành mã Python. Chúng ta cần một hàm nhận vào một danh sách và sắp xếp nó tại chỗ (in-place), nghĩa là thay đổi trực tiếp danh sách gốc thay vì tạo ra một danh sách mới.

def selection_sort(arr):
    # Lấy độ dài của danh sách
    n = len(arr)

    # Duyệt qua tất cả các phần tử của danh sách
    # Vòng lặp ngoài chạy từ đầu đến gần cuối danh sách (n-1)
    # Vì phần tử cuối cùng sẽ tự động đúng vị trí khi n-1 phần tử đầu đã được sắp xếp
    for i in range(n - 1):

        # Giả sử phần tử hiện tại (ở vị trí i) là phần tử nhỏ nhất
        # trong phần chưa được sắp xếp còn lại.
        min_index = i

        # Vòng lặp trong tìm kiếm phần tử nhỏ nhất
        # trong phần chưa được sắp xếp, bắt đầu từ vị trí i+1 đến cuối danh sách.
        for j in range(i + 1, n):
            # Nếu tìm thấy một phần tử nhỏ hơn phần tử nhỏ nhất hiện tại
            if arr[j] < arr[min_index]:
                # Cập nhật chỉ mục của phần tử nhỏ nhất mới tìm thấy
                min_index = j

        # Sau khi kết thúc vòng lặp trong, min_index chứa chỉ mục của phần tử
        # nhỏ nhất trong toàn bộ phần chưa được sắp xếp (từ i đến hết).

        # Tiến hành HOÁN ĐỔI (swap) phần tử nhỏ nhất này
        # với phần tử đầu tiên của phần chưa sắp xếp (tại vị trí i).
        # Python cho phép hoán đổi tiện lợi như sau:
        **arr[i], arr[min_index] = arr[min_index], arr[i]**

        # Sau khi hoán đổi, phần tử tại vị trí i đã đúng vị trí và thuộc về
        # phần đã sắp xếp. Vòng lặp ngoài tiếp tục với i+1.

    # Hàm không cần trả về gì vì danh sách gốc đã bị thay đổi (sắp xếp tại chỗ)

Giải Thích Code Python

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

def selection_sort(arr):: Định nghĩa một hàm có tên selection_sort nhận vào một tham số arr, là danh sách chúng ta muốn sắp xếp.
n = len(arr): Lấy độ dài của danh sách và lưu vào biến n. Điều này giúp chúng ta dễ dàng làm việc với chỉ mục và giới hạn vòng lặp.
for i in range(n - 1):: Đây là vòng lặp ngoài. Biến i đại diện cho chỉ mục của phần tử đầu tiên trong phần chưa được sắp xếp ở mỗi lượt. Vòng lặp này chạy từ 0 đến n-2. Tại sao chỉ đến n-2? Bởi vì khi chúng ta đã đặt đúng vị trí cho n-1 phần tử đầu tiên, phần tử cuối cùng (ở vị trí n-1) đương nhiên sẽ ở đúng vị trí của nó mà không cần thêm lượt xử lý nào nữa.
min_index = i: Ở đầu mỗi lượt của vòng lặp ngoài, chúng ta giả định rằng phần tử tại vị trí i (phần tử đầu tiên của phần chưa sắp xếp) là phần tử nhỏ nhất. Chúng ta lưu chỉ mục này vào biến min_index.
for j in range(i + 1, n):: Đây là vòng lặp trong. Nó bắt đầu tìm kiếm từ phần tử ngay sau arr[i] (tức là từ i+1) cho đến hết danh sách (n-1). Biến j đại diện cho chỉ mục của các phần tử mà chúng ta đang so sánh.
if arr[j] < arr[min_index]:: Bên trong vòng lặp trong, chúng ta so sánh phần tử hiện tại (arr[j]) với phần tử nhỏ nhất đã tìm thấy cho đến nay trong phần chưa được sắp xếp (arr[min_index]).
min_index = j: Nếu arr[j] nhỏ hơn arr[min_index], điều đó có nghĩa là chúng ta đã tìm thấy một phần tử nhỏ hơn phần tử nhỏ nhất trước đó. Chúng ta cập nhật min_index để trỏ đến vị trí j của phần tử mới này.
arr[i], arr[min_index] = arr[min_index], arr[i]: Đây là bước quan trọng nhất! Sau khi vòng lặp trong kết thúc (tức là chúng ta đã duyệt qua toàn bộ phần chưa được sắp xếp từ i+1 đến hết), min_index sẽ chứa chỉ mục của phần tử nhỏ nhất thực sự trong phần chưa được sắp xếp. Dòng mã này sử dụng tính năng hoán đổi tiện lợi của Python (gọi là tuple packing/unpacking) để đổi chỗ phần tử ở vị trí i (phần tử đầu tiên của phần chưa sắp xếp) với phần tử nhỏ nhất tìm được (ở vị trí min_index).
Sau khi hoán đổi, phần tử tại vị trí i đã ở đúng vị trí cuối cùng của nó trong danh sách đã sắp xếp. Vòng lặp ngoài tiếp tục, di chuyển ranh giới giữa phần đã sắp xếp và chưa sắp xếp sang phải.

Thuật toán kết thúc khi vòng lặp ngoài hoàn thành, đảm bảo rằng tất cả các phần tử đã được đặt vào đúng vị trí của chúng.

Các Ví Dụ Minh Họa

Hãy xem Selection Sort hoạt động trên các danh sách khác nhau:

Ví dụ 1: Danh sách các số nguyên dương bất kỳ

# Danh sách ban đầu
my_list_1 = [64, 25, 12, 22, 11]
print(f"Danh sách ban đầu: {my_list_1}")

# Sắp xếp danh sách sử dụng Selection Sort
selection_sort(my_list_1)

# In danh sách sau khi sắp xếp
print(f"Danh sách sau khi sắp xếp: {my_list_1}")
# Expected output: Danh sách sau khi sắp xếp: [11, 12, 22, 25, 64]

Ví dụ 2: Danh sách đã được sắp xếp

# Danh sách đã được sắp xếp
my_list_2 = [1, 2, 3, 4, 5]
print(f"\nDanh sách ban đầu (đã sắp xếp): {my_list_2}")

# Sắp xếp danh sách sử dụng Selection Sort
selection_sort(my_list_2)

# In danh sách sau khi sắp xếp
print(f"Danh sách sau khi sắp xếp: {my_list_2}")
# Expected output: Danh sách sau khi sắp xếp: [1, 2, 3, 4, 5]
# Lưu ý: Selection Sort vẫn thực hiện các bước so sánh và hoán đổi (dù là hoán đổi với chính nó)
# ngay cả khi danh sách đã được sắp xếp.

Ví dụ 3: Danh sách được sắp xếp ngược

# Danh sách được sắp xếp ngược
my_list_3 = [9, 8, 7, 6, 5]
print(f"\nDanh sách ban đầu (sắp xếp ngược): {my_list_3}")

# Sắp xếp danh sách sử dụng Selection Sort
selection_sort(my_list_3)

# In danh sách sau khi sắp xếp
print(f"Danh sách sau khi sắp xếp: {my_list_3}")
# Expected output: Danh sách sau khi sắp xếp: [5, 6, 7, 8, 9]

Ví dụ 4: Danh sách chứa các số âm và số 0

# Danh sách chứa các số âm và số 0
my_list_4 = [-5, 0, 3, -2, 1, 0]
print(f"\nDanh sách ban đầu (chứa số âm và 0): {my_list_4}")

# Sắp xếp danh sách sử dụng Selection Sort
selection_sort(my_list_4)

# In danh sách sau khi sắp xếp
print(f"Danh sách sau khi sắp xếp: {my_list_4}")
# Expected output: Danh sách sau khi sắp xếp: [-5, -2, 0, 0, 1, 3]

Ví dụ 5: Danh sách rỗng và danh sách chỉ có một phần tử

# Danh sách rỗng
my_list_5 = []
print(f"\nDanh sách ban đầu (rỗng): {my_list_5}")
selection_sort(my_list_5)
print(f"Danh sách sau khi sắp xếp: {my_list_5}")
# Expected output: Danh sách sau khi sắp xếp: []

# Danh sách chỉ có một phần tử
my_list_6 = [7]
print(f"\nDanh sách ban đầu (một phần tử): {my_list_6}")
selection_sort(my_list_6)
print(f"Danh sách sau khi sắp xếp: {my_list_6}")
# Expected output: Danh sách sau khi sắp xếp: [7]
# (Vòng lặp ngoài range(1-1) tức range(0) sẽ không chạy, danh sách giữ nguyên, là đúng)

Qua các ví dụ này, bạn có thể thấy Selection Sort hoạt động nhất quán trên nhiều loại dữ liệu khác nhau, bao gồm cả các trường hợp đặc biệt như danh sách rỗng hoặc chỉ có một phần tử.

Selection Sort là một thuật toán đơn giản và dễ hiểu, là bước khởi đầu tốt khi bạn tìm hiểu về thế giới rộng lớn của các thuật toán sắp xếp. Mặc dù có độ phức tạp thời gian là O(n^2) (do có hai vòng lặp lồng nhau, khiến số lượng thao tác tăng theo bình phương số lượng phần tử), nó vẫn hữu ích trong một số trường hợp nhất định, đặc biệt là khi số lần hoán đổi cần được giảm thiểu (vì mỗi lượt chỉ thực hiện tối đa một lần hoán đổi).

Comments

There are no comments at the moment.