Sắp xếp dữ liệu để tìm ra thứ tự hữu ích

Lan có tám phiếu điểm, trong đó có ba phiếu ghi điểm 8. Bạn cần xếp điểm từ thấp đến cao, rồi đếm số mức điểm khác nhau. Nếu nhìn từng phiếu trong thứ tự nhận được, Lan dễ đếm lặp. Sắp xếp đưa các điểm bằng nhau đứng cạnh nhau và biến việc đếm thành một lượt duyệt.

Thứ tự giúp đưa các giá trị bằng nhau lại gần

Sắp xếp (sorting) đặt các phần tử theo một quy tắc so sánh. Với các số, quy tắc quen thuộc là tăng dần: phần tử bên trái không lớn hơn phần tử bên phải. Dấu bằng được phép, vì dữ liệu có thể trùng.

Trong hình, mỗi ô là một phiếu điểm. Hàng dưới có cùng các phiếu như hàng trên, chỉ khác vị trí.

Hãy chạy chương trình sau với bốn điểm. Chương trình tạo thứ tự tăng và in lại các điểm.

scores = [8, 5, 8, 7]
scores.sort()
print(scores)

[5, 7, 8, 8]

Hai điểm 8 ở cạnh nhau. Danh sách vẫn có đủ bốn phần tử; sắp xếp không xóa bản sao. Khi gặp một điểm mới khác điểm trước, bạn biết một mức điểm mới bắt đầu.

Một dãy có n phần tử sau khi sắp có n - 1 cặp hàng xóm. Duyệt các cặp này là đủ để tìm ranh giới giữa các nhóm. Không cần so từng phần tử với tất cả phần tử khác.

sort() sửa danh sách còn sorted() tạo danh sách mới

Phương thức list.sort() thay đổi chính danh sách đang có. Hàm sorted() nhận một đối tượng có thể duyệt và trả về một list mới. Hai lựa chọn đều sắp tăng nếu không yêu cầu khác.

Chương trình sau giữ lại thứ tự phiếu ban đầu bằng sorted().

original = [9, 3, 6]
ordered = sorted(original)
print(original)
print(ordered)

[9, 3, 6]
[3, 6, 9]

Danh sách original vẫn theo thứ tự nhận phiếu. Danh sách ordered chứa cùng ba số theo thứ tự tăng. Thao tác này cần thêm bộ nhớ cho danh sách mới.

Ngược lại, ví dụ sau sửa danh sách tại chỗ. Giá trị trả về của sort() là None, không phải danh sách đã sắp.

scores = [9, 3, 6]
result = scores.sort()
print(scores)
print(result)

[3, 6, 9]
None

Nếu viết scores = scores.sort(), biến scores nhận None. Khi cần dùng kết quả ngay, hãy gọi scores.sort() riêng hoặc dùng scores = sorted(scores).

Hai biến cùng tham chiếu đến một list cũng cùng thấy thay đổi. Nếu cần một bản sao độc lập trước khi sửa, hãy tạo bằng scores.copy() hoặc sorted(scores).

scores = [4, 1, 3]
alias = scores
scores.sort()
print(alias)

[1, 3, 4]

alias không phải bản sao nên cũng thấy thứ tự mới. Phân biệt tên biến với đối tượng giúp bạn tránh mất thứ tự nhận dữ liệu ngoài ý muốn.

Chọn chiều và kiểu dữ liệu trước khi sắp

Tham số reverse=True yêu cầu thứ tự giảm dần. Nó áp dụng cho toàn bộ khóa đang được so sánh. Phương thức reverse() thì chỉ đảo vị trí hiện tại, không tự tìm thứ tự tăng hay giảm.

Hai thao tác dưới đây bắt đầu từ cùng một danh sách chưa sắp.

scores = [3, 9, 5]
backward = scores.copy()
backward.reverse()
print(backward)
print(sorted(scores, reverse=True))

[5, 9, 3]
[9, 5, 3]

Danh sách đảo chỉ đổi đầu thành cuối. Danh sách sắp giảm đặt 9 trước, rồi 5 và 3. Hai kết quả khác nhau vì dữ liệu ban đầu không tăng dần.

Dữ liệu đọc bằng input().split() là các chuỗi. Chuỗi được so sánh từ ký tự đầu, không theo giá trị số mà chuỗi biểu diễn. Chương trình sau đối chiếu hai kiểu sắp.

2 10 -3

tokens = input().split()
numbers = list(map(int, tokens))
print(sorted(tokens))
print(sorted(numbers))

['-3', '10', '2']
[-3, 2, 10]

Trong thứ tự chuỗi, ký tự 1 của 10 đứng trước ký tự 2. Sau khi đổi bằng int, các giá trị được so sánh theo số học. Hãy đọc kỹ đề: mã như 001 có thể cần giữ dạng chuỗi để không mất số 0 đầu.

key biến mỗi phần tử thành tiêu chí so sánh

Khóa sắp xếp (sort key) là giá trị đại diện dùng để so sánh một phần tử. Tham số key nhận một hàm; hàm đó nhận một phần tử và trả về khóa. Python sắp các phần tử ban đầu theo thứ tự của khóa.

Ví dụ, kho có các khoản chênh lệch âm và dương. Muốn xem khoản gần 0 trước, bạn dùng abs làm khóa.

changes = [-8, 2, -3, 5]
print(sorted(changes, key=abs))

[2, -3, 5, -8]

Các khóa lần lượt là 8, 2, 3 và 5. Chương trình in các số ban đầu, không thay chúng bằng khóa. Kết quả có số 2 trước vì khoảng cách của nó tới 0 là nhỏ nhất.

Khi nhiều phần tử có cùng khóa, cần đọc đề xem có tiêu chí phụ không. Ví dụ -3 và 3 cùng cách 0 một khoảng 3. Nếu đề yêu cầu số nhỏ hơn đứng trước, chỉ dùng key=abs chưa đủ cho mọi thứ tự đầu vào.

tuple khóa thể hiện nhiều tiêu chí theo thứ tự ưu tiên

Python so sánh hai tuple từ trái sang phải. Nếu trường đầu bằng nhau, Python mới so trường tiếp theo. Vì vậy, bạn có thể đặt tiêu chí quan trọng nhất vào vị trí đầu của khóa.

Một cuộc thi xếp điểm cao trước. Khi bằng điểm, thời gian ít hơn đứng trước. Khi vẫn bằng, mã tăng dần quyết định thứ tự.

entries = [("B", 90, 30), ("A", 90, 30),
           ("C", 100, 45), ("D", 90, 25)]
ranked = sorted(entries, key=lambda x: (-x[1], x[2], x[0]))
for entry in ranked:
    print(*entry)

C 100 45
D 90 25
A 90 30
B 90 30

Mỗi bản ghi là tuple gồm mã, điểm và thời gian. Chỉ số x[1] là điểm, còn x[2] là thời gian. Đổi dấu điểm làm điểm lớn có khóa nhỏ, nên được xếp trước khi khóa tăng dần.

Hình sau tách việc chọn khóa và sắp xếp thành hai bước. Trường cuối chỉ được xét khi hai trường trước bằng nhau.

Không dùng reverse=True cho cả tuple nếu chỉ điểm cần giảm. Cờ đó cũng đảo chiều thời gian và mã. Việc đổi dấu chỉ phù hợp với tiêu chí kiểu số; với chuỗi cần cách khác, chẳng hạn sắp ổn định nhiều lượt.

Ví dụ dưới đây ưu tiên trị tuyệt đối nhỏ, rồi ưu tiên số nhỏ khi khoảng cách bằng nhau.

values = [3, -3, 2, -2, 0]
print(sorted(values, key=lambda x: (abs(x), x)))

[0, -2, 2, -3, 3]

Khóa của -2 là (2, -2) còn khóa của 2 là (2, 2). Trường đầu bằng nhau nên trường thứ hai đưa -2 lên trước. Cách này khác với việc giữ nguyên thứ tự đầu vào khi cùng trị tuyệt đối.

Sắp xếp ổn định giữ thứ tự tương đối khi khóa bằng nhau

Tính ổn định (stability) nghĩa là hai phần tử có khóa bằng nhau vẫn giữ thứ tự tương đối ban đầu sau khi sắp. Cả sorted() và list.sort() của Python bảo đảm tính chất này, kể cả khi dùng reverse=True.

Các bạn An và Chi có cùng điểm 8. An đăng ký trước Chi, nên hai bạn giữ thứ tự đó nếu khóa chỉ là điểm.

students = [("An", 8), ("Binh", 9), ("Chi", 8)]
students.sort(key=lambda x: x[1], reverse=True)
print(students)

[('Binh', 9), ('An', 8), ('Chi', 8)]

Điểm nằm ở x[1], vì mỗi học sinh ở đây là tuple. Không gọi x.score: tuple thông thường không có thuộc tính đó. Chi không vượt An vì hai khóa cùng bằng 8.

Ổn định chỉ bảo vệ thứ tự giữa các khóa bằng nhau. Nó không tự xếp tên theo bảng chữ cái. Nếu đề yêu cầu tên tăng khi bằng điểm, hãy thêm tên vào khóa.

Có thể sắp nhiều lượt nhờ tính ổn định. Hãy sắp tiêu chí phụ trước, rồi sắp tiêu chí chính sau. Lượt cuối giữ lại thứ tự phụ bên trong từng nhóm cùng tiêu chí chính.

students = [("Chi", 8), ("An", 8), ("Binh", 9)]
students.sort(key=lambda x: x[0])
students.sort(key=lambda x: x[1], reverse=True)
print(students)

[('Binh', 9), ('An', 8), ('Chi', 8)]

Sau lượt tên, An đứng trước Chi. Lượt điểm đưa Binh lên đầu nhưng giữ An trước Chi vì hai điểm bằng nhau. Nếu sắp điểm trước rồi tên sau, tên sẽ trở thành tiêu chí chính.

Thứ tự đăng ký khác thứ tự tên. Hãy quyết định rõ đề yêu cầu loại thứ tự nào trước khi chọn key. Thêm tên vào khóa sẽ chủ động phá thứ tự đăng ký của hai bạn có tên khác nhau.

Sắp xếp rồi duyệt giúp đếm các nhóm giá trị

Trở lại tám phiếu của Lan. Ta cần số mức điểm khác nhau, không cần đếm số phiếu của từng mức. Trước tiên sắp tăng, sau đó đếm phần tử đầu và mỗi lần điểm đổi.

8
8 5 8 7 5 9 8 7

n = int(input())
scores = list(map(int, input().split()))
scores.sort()
groups = 0
for i in range(n):
    if i == 0 or scores[i] != scores[i - 1]:
        groups += 1
print(groups)

4

Các điểm bằng nhau tạo thành một đoạn liên tiếp. Phần tử đầu của mỗi đoạn là điểm đầu tiên hoặc khác điểm ngay trước. Do đó mỗi mức được đếm đúng một lần và không mức nào bị bỏ sót.

Điều kiện i == 0 được xét trước. Nhờ phép or, chương trình không cần so phần tử đầu với phần tử cuối qua chỉ số -1. Dãy rỗng có không nhóm nếu đề cho phép n = 0; ví dụ đọc ở trên giả sử có dòng điểm.

Với n = 200000, sắp xếp mất O(n log n) và một lượt đếm mất O(n). Vì log2(200000) nhỏ hơn 18, bậc tăng trưởng tương ứng khoảng 3,6 triệu đơn vị so sánh. Đây là ước lượng, không phải số phép so sánh hay thời gian chính xác.

Nếu chỉ cần số giá trị khác nhau, len(set(scores)) cũng là một cách. Sắp xếp hữu ích khi bài còn yêu cầu duyệt các nhóm theo thứ tự hoặc xử lý từng đoạn bằng nhau.

Nếu muốn biết số phiếu trong từng nhóm, bạn có thể giữ thêm số lượng của nhóm hiện tại. Bắt đầu từ phần tử đầu; khi gặp cùng giá trị, tăng số lượng. Khi giá trị đổi, ghi nhận nhóm vừa kết thúc rồi bắt đầu nhóm mới.

Đừng quên xử lý nhóm cuối sau vòng lặp, vì không còn phần tử tiếp theo để báo ranh giới. Một dãy toàn điểm bằng nhau chỉ có một nhóm. Một dãy gồm một điểm cũng có một nhóm, dù vòng kiểm tra các cặp kề không chạy lần nào.

Nếu dãy đã tăng sẵn, thao tác sắp lại không cần thiết cho việc gom nhóm. Nhưng khi đề không bảo đảm thứ tự đầu vào, hãy sắp trước hoặc dùng một cấu trúc đếm phù hợp. Kiểm tra điều kiện của từng phương pháp quan trọng hơn việc thuộc một mẫu code có sẵn.

Ghép hai số kề nhau để giảm tổng khoảng cách

Một cửa hàng có số chẵn thanh gỗ. Mỗi cặp cần hai thanh gần nhau về chiều dài để giảm phần chênh lệch. Mục tiêu là tổng độ chênh lệch của mọi cặp nhỏ nhất.

Với bốn thanh có thứ tự a ≤ b ≤ c ≤ d, ghép (a, b) và (c, d) có tổng (b - a) + (d - c). Ghép chéo (a, c) và (b, d) lớn hơn hoặc bằng vì thêm hai lần khoảng c - b. Ghép ngoài (a, d) và (b, c) cũng không nhỏ hơn.

Lập luận đổi cặp này áp dụng cho hai cặp bất kỳ. Trong một cách ghép tối ưu, nếu thanh nhỏ nhất chưa đi với thanh kế bên, ta đổi hai cặp chứa chúng mà không tăng tổng. Lặp lại trên phần còn lại cho thấy ghép các phần tử kề nhau là đủ.

Chương trình sau đọc sáu độ dài và cộng hiệu giữa hai thanh trong từng cặp kề sau khi sắp.

6
9 1 5 4 10 2

n = int(input())
lengths = list(map(int, input().split()))
lengths.sort()
cost = 0
for i in range(0, n, 2):
    cost += lengths[i + 1] - lengths[i]
print(cost)

3

Sau khi sắp, mỗi hiệu đều không âm. Có đúng n / 2 cặp và mỗi thanh xuất hiện một lần. Bước sắp có độ phức tạp O(n log n); bước ghép là O(n).

Với n = 200000, sắp xếp theo bậc khoảng 200000 × 18, còn vòng ghép chỉ có 100000 lượt. Nếu thử mọi cách ghép, số phương án tăng rất nhanh và không phù hợp kích thước này. Lập luận đổi cặp là điều giúp ta tránh thử hết.

Chọn phương pháp theo câu hỏi sau khi sắp

Sắp xếp là một bước xử lý, không luôn là toàn bộ lời giải. Thứ tự vừa tạo có thể giúp bạn nhìn thấy cấu trúc của dữ liệu. Nhưng thay đổi thứ tự cũng làm mất quan hệ vị trí ban đầu nếu bạn không lưu thêm chỉ số.

Nếu đề hỏi vị trí ban đầu sau khi sắp, hãy lưu chỉ số cùng giá trị. Ví dụ sau đánh số từ 1 theo thứ tự nhập, rồi sắp theo giá trị.

values = [7, 2, 7, 4]
indexed = [(value, i + 1) for i, value in enumerate(values)]
indexed.sort(key=lambda item: item[0])
for value, position in indexed:
    print(value, position)

2 2
4 4
7 1
7 3

Hai giá trị 7 vẫn theo thứ tự vị trí 1 rồi 3 nhờ tính ổn định. Chỉ số được lưu trước khi sắp, nên mỗi bản ghi vẫn mang theo nguồn gốc. Nếu đề yêu cầu chỉ số giảm khi bằng giá trị, bạn phải thêm tiêu chí đó vào khóa.

Lỗi thường gặp

Tóm tắt

• sort() sửa list và trả None; sorted() tạo list mới.
• key tạo khóa so sánh; tuple khóa xét các trường từ trái sang phải.
• Sắp xếp ổn định giữ thứ tự tương đối khi toàn bộ khóa bằng nhau.
• Sắp xếp rồi duyệt giúp gom nhóm và ghép cặp kề, nhưng cần chứng minh bước sau phù hợp đề.
• Với n lớn, ước lượng O(n log n) cùng chi phí đọc, bộ nhớ và bước xử lý tiếp theo.

Kiểm tra nhanh

Đọc thêm

• Python Sorting HOW TO: khóa, chiều và tính ổn định.
• Python list.sort(): cách sửa danh sách và giá trị trả về.