Sorting in Python

 Bữa giờ sort trong Python nhiều nay mới có cơ hội tìm hiểu về nó :)

Sorting algorithm được sử dụng trong hầu hết Python implementations được gọi là timsort (1).
Ý tưởng chủ đạo là tận dụng lợi thế đó là trong rất nhiều tập hợp dữ liệu thì một phần dữ liệu nào đó đã được sắp xếp. Hiệu suất tệ nhất của Tim sort là giống như merge sort, nhưng trong trường hợp trung bình nó thực hiện tốt hơn.

Phương thức list.sort lấy một list là đối số đầu tiên của nó và thay đổi list đó. Ngược lại, hàm sorted có đối số đầu tiên là iterable object (ví dụ như một list  hoặc dictionary) và trả về một list mới đã được sắp xếp. Cho ví dụ, code sau

L = [3, 5, 2]
D = {'a':12, 'c':5, 'b':'dog'}
print(sorted(L))
print(L)
L.sort()
print(L)
print(sorted(D))
D.sort()

Chúng ta nhận được kết quả
[2, 3, 5]
[3, 5, 2]
[2, 3, 5]
D.sort()
Traceback (most recent call last):
  File "<pyshell#60>", line 1, in <module>
    D.sort()
AttributeError: 'dict' object has no attribute 'sort'

Chúng ta rút ra một vài điều thú vị như sau: khi ta sử dụng hàm sorted() thì list ban đầu không bị thay đổi, trái lại nếu sử dụng phương thức sẽ thay đổi list ban đầu. Đối tượng từ điển không có thuộc tính 'sort' nghĩa là chúng ta không thể áp dụng phương thức sort đối với một đối tượng từ điển. Nhưng đối với sorted() thì ta có thể.

Cả list.sort method và sorted function có thể có thêm 2 đối số nữa. key parameter và reverse parameter. reverse parameter xác định xem list sẽ được sắp xếp theo thứ tự tăng dần hay là giảm dần.

Ví dụ:
L = [[1, 2, 3], (3, 2, 1), (3, 1)]
print(sorted(L, key = len, reverse = False))

Kết quả:
[(3, 1), [1, 2, 3], (3, 2, 1)]

Trong ví dụ trên ta xác định key = len nghĩa là nó sẽ sắp xếp theo độ dài và theo thứ tự ngược lại.

Cả list.sort method và sorted function cung cấp stable sorts. Điều đó có nghĩa là nếu hai phần tử là bằng nhau thì thứ tự của hai phẩn tử đó trong list ban đầu sẽ quyết định trong list kết quả.