Python: Sắp xếp (sorting)

Sắp xếp

Sắp xếp là thao tác thường xuyên khi ta sử dụng phần mềm (ví dụ như trong excel ta sắp xếp các bản ghi theo rất nhiều tiêu chí mà ta mong đợi). Trong bài này, mình sẽ hướng dẫn các hàm sắp xếp được xây dựng sẵn của Python. Các post sau chúng ta sẽ tự xây dựng thuật toán sắp xếp cho riêng mình (các thuật toán sắp xếp gồm có: sắp xếp nổi bọt, chèn, chọn, nhanh,...)

Bài toán: cho một danh sách hãy sắp xếp lại danh sách theo một trật tự nào đó được yêu cầu (tăng, giảm).

Trước và sau sắp xếp

Hàm sorted

Cú pháp của hàm sorted như sau:

sorted(iterable, key=None, reverse=False)

Từ cú pháp, ta thấy hàm sorted có ba tham số là: iterable, key và reverse. Trong đó, hai tham số cuối được gán giá trị mặc định là None và False. Tham số iterable là chính là List mà ta muốn sắp xếp. Kết quả trả về của nó sẽ là một mảng mới với các phần tử được lấy từ mảng truyền vào nhưng được sắp thứ tự như ta mong muốn.

Hãy chạy code trên và quan sát kết quả. Ta thấy chỉ có list b là được sắp xếp còn list a vẫn giữ nguyên như cũ.
Bây giờ, nếu muốn kết quả nhận được của hàm sorted là một mảng được sắp xếp theo chiều ngược lại thì làm thế nào? Từ cú pháp của hàm sorted ta thấy ngay là chỉ cần thay đổi tham số reverse thành True là sẽ được kết quả như mong muốn đúng không? Hãy xem code dưới đây: Bây giờ, list b vẫn chứa các dữ liệu của list a nhưng thứ tự được đổi lại đúng không nào?
Hai ví dụ trên, dữ liệu của chúng ta là số nên ta sẽ xắp xếp theo kiểu số học, trong các trường hợp khác dữ liệu kiểu khác thì làm thể nào để sắp xếp? Rõ ràng, ta cần biết tiêu chi để sắp xếp và khi biết tiêu chí đó rồi thì làm thế nào triển khai được.
Bây giờ, ta xét một list các chuỗi. Ta thực hiện sắp xếp chúng theo trật tự chứ cái nhé. Hãy xem ví dụ sau.
Khi chạy chương trình, mảng ban đầu sẽ được sắp xếp theo trật tự từ điển. Nhưng bây giờ, mình muốn sắp xếp theo độ dài của các xâu thì thế nào?Hãy xem đoạn code dưới đây.
Khác với ví dụ trên, ta sử dụng tham số key trong hàm sorted và gán key=len. Vậy len ở đây là gì? Có còn cái nào khác ngoài len nữa không? Xin trả lời, len là một hàm được dựng sẵn và có một tham số có kiểu tương ứng với kiểu của các phần tử trong list. Khi thực hiện so sánh, chương trình sử dụng kết quả của len với các tham số tương ứng vào để so sánh.
Vậy, có nhiều hàm tương tự hàm len hay không? Có rất nhiều hàm, chỉ cần tham số truyền vào có kiểu là kiểu của các phần tử trong danh sách. Như vậy, ta hoàn toàn có thể định nghĩa cách hàm này. Ví dụ, bây giờ muốn mình muốn sắp xếp một danh sách các chuỗi theo chiều ký tự cuối cùng tăng dần. Ta làm như sau:
Bước 1: Xem xét có hàm nào có 1 tham số là chuỗi và trả về phần tử cuối cùng của chuỗi hay không? Không có thì chuyển bước 2.
Bước 2: Ta sẽ tự định nghĩa một hàm cho phép trả về ký tự cuối cùng của chuỗi. Hàm này sẽ đơn giản như sau:
Hàm getLastCharacter rất đơn giản đúng không? Chỉ có một tham số đầu vào thôi và kết quả trả ra "ký tự" cuối cùng của chuỗi (bạn biết cách đánh chỉ số âm của python chứ?). Bây giờ, chương trình đầy đủ sẽ như sau:
Chạy chương trình và bạn sẽ thấy, ký tự cuối cùng của mỗi phần tử trong danh sách được xắp xếp theo chiều tăng dần (d, o, e, r).

Phương thức sort

Ta thấy có 2 cách gọi khác nhau là hàm và phương thức. Hàm sorted được xây dựng theo hướng thủ tục và kết quả trả về là một danh sách được sắp xếp chứ không phải sắp xếp lại chính bản thân của danh sách được truyền vào. Ngược lại, phương thức sort được xây dựng theo hướng đối tượng và khi thực hiện hàm này thì bản thân các phần tử trong mảng được sắp xếp lại chứ phương thức này không có kết quả trả về.

Ta xem cú pháp của phương thức này như sau:

iterable.sort(key=None, reverse=False)

Phương thức này có 2 tham số là key và reverse với ý nghĩa tương tự như trên. iterable lúc này không còn là tham số nữa mà được coi là một đối tượng (bạn tự trả cứu lập trình hướng đối tượng là gì nhé). Đầu tiên, ta xem một ví dụ như sau:

Rõ ràng, lúc này ta không cần đến mảng b nữa mà bản thân trong mảng a tự thay đổi vị trí của các phần tử.
Hai tham số reverse và key tương tự như trong hàm sorted.

Kết luận

Vậy trong bài này chúng ta đã tìm hiểu hai cách sắp xếp một danh sách. Tuy nhiên, chúng ta chưa thực sự biết thuật toán nào được áp dụng trong các hàm trên. Post sau chúng ta sẽ đi cài đặt các thuật toán sắp xếp bằng ngôn ngữ lập trình python nhé.
Bạn có thể xem code đầy đủ tại đây.