Sắp xếp lựa chọn trong Python chia một danh sách thành hai danh sách nhỏ. Một danh sách đại diện cho các phần tử được sắp xếp. Danh sách còn lại chứa các phần tử chưa được sắp xếp. Sắp xếp lựa chọn tìm các giá trị nhỏ nhất hoặc cao nhất trong mỗi lần lặp và di chuyển các giá trị đó vào danh sách có thứ tự.
Sắp xếp danh sách là một thao tác phổ biến trong nhiều chương trình.
Hãy xem xét ví dụ này:Một giáo viên muốn tìm hiểu thêm về việc học sinh của họ đã làm tốt như thế nào trong bài kiểm tra gần đây nhất của họ. Một giáo viên có thể muốn sắp xếp điểm số của học sinh theo thứ tự tăng dần và giảm dần. Điều này sẽ giúp họ dễ dàng tìm ra điểm kiểm tra cao nhất và thấp nhất.
Enter, sắp xếp lựa chọn. Sắp xếp lựa chọn là một thuật toán mà bạn có thể sử 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, chúng ta sẽ thảo luận về cách viết chương trình sắp xếp lựa chọn bằng Python. Chúng tôi sẽ đi qua một ví dụ trong suốt hướng dẫn này để bạn có thể tìm hiểu chi tiết về các loại lựa chọn.
Sắp xếp lựa chọn Python là gì?
Sắp xếp lựa chọn Python lặp đi lặp lại tìm phần tử tối thiểu trong danh sách và di chuyển phần tử đó đến một phần cuối cụ thể của danh sách. Việc 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ể hướng dẫn sắp xếp lựa chọn để tìm phần tử tối đa. Cả hai cách tiếp cận đều sắp xếp một danh sách.
Các loại lựa chọn giả định rằng phần tử đầu tiên trong danh sách là giá trị nhỏ nhất. Sau đó, 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ị nhỏ nhất, phần tử thứ hai sẽ trở thành giá trị nhỏ nhất.
Quá trình này được lặp lại cho đến khi đạt đến phần tử cuối cùng của danh sách. Khi đạt đến phần tử này, giá trị tối thiểu được đặt ở đầu danh sách chưa được sắp xếp.
81% người tham gia cho biết họ cảm thấy tự tin hơn về triển vọng công việc công nghệ của mình sau khi tham gia chương trình đào tạo. Kết hợp với bootcamp ngay hôm nay.
Sinh viên tốt nghiệp bootcamp trung bình dành ít hơn sáu tháng để chuyển đổi nghề nghiệp, từ khi bắt đầu bootcamp đến khi tìm được công việc đầu tiên của họ.
Hướng dẫn sắp xếp lựa chọn Python
Không có cách nào tốt hơn để tìm hiểu về các loại lựa chọn hơn là xem qua một ví dụ. Hãy xem qua và sắp xếp danh sách các điểm của sinh viên theo thứ tự tăng dần. Hãy xem xét danh sách chưa được sắp xếp này:
| 73 | 62 | 61 | 69 |
Chúng tôi sẽ bắt đầu bằng cách gọi giá trị đầu tiên trong danh sách của chúng tôi là tối thiểu . Mỗi lần lặp lại sắp xếp lựa chọn sẽ tìm phần tử nhỏ nhất và 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. Sắp xếp lựa chọn hoạt động nếu bạn sắp xếp phần tử tối đa. Tuy nhiên, chúng tôi đang sử dụng phần tử tối thiểu trong ví dụ này.
Tiếp theo, chúng tôi sẽ so sánh giá trị nhỏ nhất với phần tử thứ hai. Nếu phần tử này nhỏ hơn giá trị tối thiểu, phần tử thứ hai sẽ trở thành giá trị nhỏ nhất.
Chúng ta sẽ so sánh 73 và 62. 73 lớn hơn 62, có nghĩa là giá trị nhỏ nhất mới của chúng ta là 62. Sau đó, danh sách của chúng ta sẽ đi qua tất cả các số khác trong danh sách của chúng ta:
- 61 có lớn hơn 62 (giá trị nhỏ nhất của chúng tôi) không? Không, vì vậy hãy hoán đổi các số. Tối thiểu trở thành 61.
- 69 có lớn hơn 61 (giá trị nhỏ nhất của chúng tôi) không? Vâng, vì vậy không làm gì cả. Mức tối thiểu là 61.
Danh sách của chúng tôi trông giống nhau:
| 73 | 62 | 61 | 69 |
Khi bạn đến cuối danh sách, bạn có thể di chuyển tối thiểu đến đầu danh sách:
| 61 | 73 | 62 | 69 |
61 (giá trị nhỏ nhất của chúng tôi) đã được chuyển lên đầu danh sách và mọi giá trị khác đã tăng lên một giá trị. Chúng tôi sẽ lặp lại quy trình này cho đến khi tất cả các yếu tố được sắp xếp.
Mỗi lần lặp lại danh sách của chúng tôi sẽ trả về như sau:
- 73, 62, 61, 69
- 61, 73, 62, 69
- 61, 62, 73, 69
- 61, 62, 69, 73
Khi sắp xếp lựa chọn đã kiểm tra tất cả các phần tử trong danh sách, sắp xếp sẽ dừng lại.
Mảng con được sắp xếp và mảng con không được sắp xếp đều không thể nhìn thấy được đối với chúng tôi. Thuật toán của chúng tôi sắp xếp một mảng cho chúng tôi và theo dõi phần chưa được sắp xếp của mảng.
Cách thực hiện sắp xếp lựa chọn trong Python
Bây giờ bạn đã quen với lý thuyết:làm tốt lắm! Đã đến lúc cho thử thách lớn. Chúng tôi sẽ triển khai thuật toán sắp xếp lựa chọn bằng Python. Hãy viết một chương trình sử dụng một mảng Python và sắp xếp nó theo thứ tự tăng dần.
Xác định chức năng sắp xếp
Chúng ta sẽ bắt đầu bằng cách xác định một hàm Python thực hiện sắp xếp lựa chọn của chúng ta:
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])
Chúng tôi đã bắt đầu bằng cách sử dụng phương thức Python len () để lấy độ dài của danh sách của chúng tôi. Sau đó, chúng tôi sử dụng điều này để bắt đầu một Python for lặp lại lặp lại mọi mục trong danh sách của chúng tôi.
Đối với mỗi lần lặp trong vòng lặp, chúng tôi đặt giá trị là tối thiểu là mục đầu tiên trong danh sách của chúng tôi. Chúng tôi đã làm điều này trong hướng dẫn của chúng tôi trước đó. Khi chúng tôi đã đặt một giá trị tối thiểu, một giá trị khác cho bắt đầu vòng lặp chạy qua mọi mục trong danh sách của chúng tôi.
Đối với mỗi mục trong danh sách, thuật toán của chúng tôi sẽ kiểm tra xem giá trị nhỏ nhất có lớn hơn mục đó hay không. Nếu đúng như vậy, không có gì xảy ra; nếu không, giá trị nhỏ nhất sẽ trở thành mục mà chương trình đang đọc.
Khi lặp lại mọi mục trong danh sách của chúng tôi, thuật toán của chúng tôi sẽ di chuyển giá trị nhỏ nhất lên đầu danh sách. Sau đó, chương trình của chúng tôi sẽ tiếp tục cho đến đầu cho vòng lặp kết thúc. Điều này là do việc sắp xếp lựa chọn chạy một số lần bằng độ dài của danh sách.
Gọi hàm sắp xếp
Bạn có thể nhận thấy rằng nếu chúng tôi chạy chương trình của mình, không có gì xảy ra. Điều này là do chúng tôi vẫn chưa cho mã của mình biết những giá trị nào cần sử dụng. Thêm mã sau vào cuối chương trình của bạn, bên ngoài hàm sortList:
numbers = [73, 62, 61, 69]
sortList(numbers)
print("Sorted list:", numbers)
Khi chúng tôi chạy chương trình của mình, thông tin sau được trả về:
[61, 62, 69, 73]
Danh sách của chúng tôi đã được sắp xếp. Tự vỗ nhẹ vào lưng; bạn đã làm được!
Sắp xếp lựa chọn có thể được sử dụng để sắp xếp danh sách theo thứ tự giảm dần. Nếu bạn muốn sắp xếp danh sách theo cách này, bạn có thể thay đổi câu lệnh “if” trong sắp xếp lựa chọn thành như sau:
if array[i] > array[minimum]:
Chúng tôi đã thay đổi dấu hiệu nhỏ hơn thành dấu hiệu lớn hơn. Điều này sẽ sắp xếp danh sách của chúng tôi theo thứ tự giảm dần, vì giá trị nhỏ nhất sẽ được đặt thành giá trị cao nhất trong danh sách. Về mặt kỹ thuật, tối thiểu của chúng tôi giá trị trở thành tối đa giá trị.
Khi nào bạn nên sử dụng sắp xếp lựa chọn?
Các loại lựa chọn, như sắp xếp bong bóng, được sử dụng tốt nhất cho các danh sách nhỏ hơn. Điều này là do thuật toán không hiệu quả bằng các thuật toán khác, chẳng hạn như sắp xếp chèn khi được sử dụng trên các danh sách lớn hơn.
Sắp xếp lựa chọn là một cách tuyệt vời để tìm hiểu khi bạn mới bắt đầu với các thuật toán sắp xếp. Các cách sắp xếp khác có thể khó thành thạo, nhưng hiểu rõ về các cách sắp xếp lựa chọn có thể giúp bạn hiểu các loại danh sách khác nhau.
Độ phức tạp của Sắp xếp Lựa chọn là gì?
Sắp xếp lựa chọn có độ phức tạp thời gian là O (n2). Điều này có nghĩa là độ phức tạp của thuật toán sẽ tăng lên theo cấp số nhân tùy thuộc vào số lượng phần tử trong danh sách.
O (n2) là độ phức tạp trong trường hợp xấu nhất, trung bình và trường hợp tốt nhất cho thuật toán này. Nếu bạn muốn tìm hiểu thêm về cách sắp xếp phức tạp, hãy xem hướng dẫn của chúng tôi về Ký hiệu Big O.
Kết luận
Sắp xếp lựa chọn là một phương pháp sắp xếp dữ liệu quan trọng. Lựa chọn sắp xếp đọc qua mọi mục trong danh sách và trên mỗi lần lặp lại, di chuyển mục nhỏ nhất đến đầu danh sách. Điều này xảy ra cho đến khi mọi mục trong danh sách được đọc.
Việc sắp xếp lựa chọn không được sử dụng rộng rãi ngoài việc giảng dạy vì có nhiều thuật toán hiệu quả hơn để sử dụng. Như đã nói, chúng là một bàn đạp tốt để học các kiểu khác, chẳng hạn như sắp xếp chèn hoặc hợp nhất.
Bạn có muốn tìm hiểu thêm về Python? Đọc hướng dẫn Cách học Python đầy đủ của chúng tôi để có lời khuyên từ chuyên gia nhằm giúp bạn nâng cao kiến thức của mình.