Selection Sort Python: Hướng dẫn chi tiết

Selection sort trong Python chia danh sách thành hai danh sách nhỏ. Một danh sách biểu diễn các phần tử đã sắp xếp. Danh sách kia chứa các phần tử chưa sắp xếp. Selection sort tìm giá trị nhỏ nhất hoặc lớn nhất trong mỗi lần lặp và di chuyển các giá trị đó vào danh sách đã sắp xếp.

Sắp xếp danh sách là thao tác phổ biến trong nhiều chương trình.

Xét ví dụ: Một giáo viên muốn biết học sinh làm bài kiểm tra gần đây như thế nào. Giáo viên có thể muốn sắp xếp điểm số theo thứ tự tăng dần và giảm dần. Điều này giúp dễ dàng tìm điểm cao nhất và thấp nhất.

Đó là lúc selection sort xuất hiện. Selection sort là thuật toán bạn có thể dùng để sắp xếp danh sách theo thứ tự tăng dần hoặc giảm dần.

Trong hướng dẫn này, ta sẽ thảo luận cách viết chương trình selection sort trong Python. Ta sẽ đi qua ví dụ xuyên suốt hướng dẫn để bạn nắm rõ selection sort.

Selection Sort trong Python là gì?

Selection sort Python liên tục tìm phần tử nhỏ nhất trong danh sách và di chuyển phần tử đó đến một đầu cụ thể của danh sách. Sắp xếp tiếp tục cho đến khi mảng được sắp xếp theo thứ tự. Bạn cũng có thể yêu cầu selection sort tìm phần tử lớn nhất. Cách nào cũng sắp xếp danh sách.

Selection sort giả định phần tử đầu tiên trong danh sách là giá trị nhỏ nhất. Sắp xếp sẽ so sánh giá trị đó với phần tử thứ hai. Nếu phần tử thứ hai nhỏ hơn giá trị tối thiểu, phần tử thứ hai trở thành giá trị tối thiểu mới.

Quá trình này lặp lại cho đến khi đến phần tử cuối cùng của danh sách. Khi đến phần tử cuối, giá trị tối thiểu được đặt ở đầu danh sách chưa sắp xếp.

Hướng dẫn Selection Sort Python

Không có cách tốt hơn học selection sort hơn là chạy qua ví dụ. Hãy sắp xếp danh sách điểm học sinh theo thứ tự tăng dần. Xét danh sách chưa sắp xếp:

Ta bắt đầu gọi giá trị đầu tiên của danh sách là minimum. Mỗi lần lặp của selection sort sẽ tìm phần tử nhỏ nhất và di chuyển nó vào mảng con đã sắp xếp.

Sắp xếp phần tử tối thiểu là một tùy chọn. Selection sort hoạt động nếu bạn sắp xếp phần tử tối đa. Nhưng trong ví dụ này ta dùng phần tử tối thiểu.

Tiếp theo, ta so sánh giá trị tối thiểu với phần tử thứ hai. Nếu phần tử này nhỏ hơn minimum, nó nên trở thành giá trị minimum mới.

Ta so sánh 73 và 62. 73 lớn hơn 62, nghĩa là giá trị minimum mới là 62. Danh sách sẽ đi qua các số còn lại:

61 có lớn hơn 62 (giá trị minimum) không? Không, nên đổi chỗ. Minimum thành 61.
69 có lớn hơn 61 (giá trị minimum) không? Có, nên không làm gì. Minimum giữ ở 61.

Danh sách trông giống nhau:

Khi đến cuối danh sách, bạn có thể di chuyển minimum lên đầu danh sách:

61 (giá trị minimum) đã được di chuyển lên đầu danh sách, và mọi giá trị khác dịch lên một vị trí. Ta sẽ lặp lại quá trình cho đến khi tất cả phần tử được sắp xếp.

Mỗi lần lặp danh sách sẽ trả về:

73, 62, 61, 69
61, 73, 62, 69
61, 62, 73, 69
61, 62, 69, 73

Khi selection sort đã kiểm tra tất cả phần tử, sắp xếp sẽ dừng.

Mảng con đã sắp xếp và mảng con chưa sắp xếp đều vô hình với chúng ta. Thuật toán sắp xếp mảng cho chúng ta và theo dõi phần chưa sắp xếp.

Cách thực hiện Selection Sort trong Python

Bây giờ bạn đã nắm lý thuyết: tốt lắm! Đã đến lúc thử thách lớn. Ta sẽ triển khai thuật toán selection sort trong Python. Hãy viết chương trình nhận mảng Python và sắp xếp theo thứ tự tăng dần.

Định nghĩa hàm sắp xếp

Ta bắt đầu bằng định nghĩa hàm Python thực hiện selection sort:

def sortList(array):
    length = len(array)
    for item in range(length):
        minimum = item
        for i in range(item + 1, length):
            if array[i] < array[minimum]:
                minimum = i
        (array[item], array[minimum]) = (array[minimum], array[item])

Ta bắt đầu dùng len() của Python lấy độ dài danh sách. Ta dùng độ dài này khởi tạo vòng lặp for duyệt qua mọi mục trong danh sách.

Đối với mỗi lần lặp, ta đặt giá trị minimum là mục đầu tiên trong danh sách. Ta đã làm điều này trong phần giải thích trước. Khi đã đặt giá trị minimum, một vòng lặp for khác bắt đầu chạy qua mọi mục trong danh sách.

Đối với mỗi mục, thuật toán kiểm tra nếu giá trị minimum lớn hơn mục đó. Nếu có, không xảy ra gì; ngược lại, giá trị minimum trở thành mục mà chương trình đang đọc.

Sau khi lặp qua mọi mục, thuật toán di chuyển giá trị minimum lên đầu danh sách. Chương trình tiếp tục cho đến khi vòng lặp for ngoài cùng kết thúc. Điều này vì selection sort chạy số lần bằng độ dài danh sách.

Gọi hàm sắp xếp

Bạn có thể nhận ra nếu chạy chương trình, không có gì xảy ra. Điều này vì ta chưa nói cho mã biết dùng giá trị nào. Thêm mã sau vào cuối chương trình, bên ngoài hàm sortList:

numbers = [73, 62, 61, 69]
sortList(numbers)
print("Danh sách đã sắp xếp:", numbers)

Khi chạy chương trình, kết quả trả về:

[61, 62, 69, 73]

Danh sách đã được sắp xếp. Thật tuyệt vời; bạn đã làm được!

Selection sort có thể dùng để sắp xếp danh sách theo thứ tự giảm dần. Nếu muốn sắp xếp theo cách này, bạn có thể thay đổi câu lệnh "if" trong selection sort thành:

if array[i] > array[minimum]:

Ta đã đổi dấu nhỏ hơn thành dấu lớn hơn. Điều này sẽ sắp xếp danh sách theo thứ tự giảm dần, vì giá trị minimum sẽ được đặt thành giá trị lớn nhất trong danh sách. Về mặt kỹ thuật, giá trị minimum trở thành giá trị maximum.

Khi nào nên dùng Selection Sort?

Selection sort, như bubble sort, phù hợp nhất cho danh sách nhỏ. Điều này vì thuật toán không hiệu quả bằng các thuật toán khác như insertion sort khi dùng trên danh sách lớn.

Selection sort là thuật toán sắp xếp tốt để học khi bạn mới bắt đầu với thuật toán sắp xếp. Các thuật toán khác có thể khó nắm vững, nhưng hiểu rõ selection sort giúp bạn hiểu các loại danh sách khác.

Độ phức tạp của Selection Sort là gì?

Selection sort có độ phức tạp thời gian O(n²). Nghĩa là độ phức tạp thuật toán sẽ tăng theo cấp số nhân tùy thuộc vào số phần tử trong danh sách.

O(n²) là độ phức tạp xấu nhất, trung bình, và tốt nhất cho thuật toán này. Nếu muốn tìm hiểu thêm về độ phức tạp sắp xếp, xem hướng dẫn Ký hiệu Big O của chúng tôi.

Kết luận

Selection sort là phương pháp quan trọng để sắp xếp dữ liệu. Selection sort đọc qua mọi mục trong danh sách và, mỗi lần lặp, di chuyển mục nhỏ nhất lên đầu danh sách. Điều này xảy ra cho đến khi mọi mục đã được đọc.

Selection sort không được dùng rộng rãi ngoài giảng dạy vì có thuật toán hiệu quả hơn. Tuy nhiên, chúng là điểm khởi đầu tốt để học các thuật toán khác như insertion sort hoặc merge sort.

Bạn quan tâm tìm hiểu thêm về Python? Đọc hướng dẫn hoàn chỉnh "Cách học Python" để có lời khuyên chuyên gia giúp bạn nâng cao kiến thức.