Trong lập trình Python, List là một trong những kiểu dữ liệu linh hoạt và được sử dụng nhiều nhất. Một List có thể chứa số, chuỗi, đối tượng… và thường xuyên chúng ta cần sắp xếp các phần tử trong List để tiện xử lý hoặc hiển thị.
Ví dụ: bạn có một danh sách điểm thi của sinh viên, bạn cần sắp theo điểm cao → thấp; hoặc một danh sách tên, cần sắp theo thứ tự alphabet.
Trong bài này, mình sẽ cùng tìm hiểu chi tiết cách sắp xếp các phần tử trong List bằng:
- Hàm dựng sẵn trong Python (
sort(),sorted()). - Tự triển khai thuật toán sắp xếp để hiểu bản chất.
- So sánh các thuật toán, nêu ra tình huống áp dụng.
- Sai lầm thường gặp và ứng dụng thực tế khi làm việc với List.
1. Tổng quan về List và Sorting
- List trong Python: là cấu trúc dữ liệu động, có thể chứa nhiều kiểu phần tử, thay đổi kích thước linh hoạt, hỗ trợ thao tác thêm/xóa/sửa dễ dàng.
- Sorting (sắp xếp): là việc đưa các phần tử trong List về một thứ tự xác định.
- Thường gặp: tăng dần (ascending), giảm dần (descending).
- Ngoài ra có thể tùy chỉnh (ví dụ sắp chuỗi theo độ dài).
Lợi ích của việc sắp xếp List:
- Giúp tìm kiếm nhanh hơn (binary search).
- Dữ liệu trở nên dễ đọc và dễ phân tích.
- Là bước trung gian quan trọng trong nhiều thuật toán khác.
2. Sắp xếp List bằng hàm dựng sẵn trong Python
Python cung cấp sẵn hai công cụ mạnh mẽ:
list.sort()— sắp xếp in-place, thay đổi List gốc.sorted(list)— trả về List mới đã sắp xếp, List gốc không đổi.
Ví dụ minh họa
numbers = [7, 2, 9, 4]
# Sort in ascending order (default)
numbers.sort()
print(numbers) # [2, 4, 7, 9]
# Sort in descending order
numbers.sort(reverse=True)
print(numbers) # [9, 7, 4, 2]
# Using sorted() to keep original list
original = [3, 1, 2]
new_sorted = sorted(original)
print(original) # [3, 1, 2]
print(new_sorted) # [1, 2, 3]
# Custom sorting: sort strings by length
words = ["apple", "kiwi", "banana"]
words.sort(key=len)
print(words) # ['kiwi', 'apple', 'banana']
Giải thích
list.sort()thường nhanh hơn một chút vì không tạo ra List mới.sorted()hữu ích khi bạn muốn giữ nguyên dữ liệu ban đầu.- Cả hai đều sử dụng Timsort (trung bình O(n log n), stable).
key=cho phép bạn định nghĩa cách so sánh (ví dụ theo độ dài chuỗi, theo điểm số).reverse=Trueđể sắp xếp ngược.
3. Các thuật toán sắp xếp phổ biến cho List
Dù có sẵn sort() và sorted(), nhưng việc hiểu thuật toán cơ bản giúp bạn nắm rõ bản chất, có thể tối ưu trong trường hợp đặc thù.
3.1 Bubble Sort
Ý tưởng: So sánh từng cặp kề nhau, đổi chỗ nếu sai thứ tự, lặp lại đến khi mảng được sắp.
def bubble_sort(lst):
n = len(lst)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if lst[j] > lst[j + 1]:
# Swap elements
lst[j], lst[j + 1] = lst[j + 1], lst[j]
swapped = True
if not swapped:
break
return lst
print(bubble_sort([5, 3, 8, 4]))
# Output: [3, 4, 5, 8]
Độ phức tạp: O(n²). Thích hợp cho học thuật, không phù hợp dataset lớn.
3.2 Selection Sort
Ý tưởng: Ở mỗi vòng lặp, chọn phần tử nhỏ nhất trong List còn lại và đưa về đầu.
def selection_sort(lst):
n = len(lst)
for i in range(n):
min_index = i
for j in range(i + 1, n):
if lst[j] < lst[min_index]:
min_index = j
lst[i], lst[min_index] = lst[min_index], lst[i]
return lst
print(selection_sort([64, 25, 12, 22, 11]))
# Output: [11, 12, 22, 25, 64]
Độ phức tạp: O(n²). Không stable.
3.3 Insertion Sort
Ý tưởng: Duyệt từ trái sang phải, chèn phần tử hiện tại vào vị trí đúng trong đoạn đã sắp.
def insertion_sort(lst):
for i in range(1, len(lst)):
key = lst[i]
j = i - 1
while j >= 0 and lst[j] > key:
lst[j + 1] = lst[j]
j -= 1
lst[j + 1] = key
return lst
print(insertion_sort([12, 11, 13, 5, 6]))
# Output: [5, 6, 11, 12, 13]
Độ phức tạp: Trung bình O(n²), tốt nhất O(n) (nếu gần sắp xếp). Stable.
3.4 Quick Sort
Ý tưởng: Chọn một pivot, chia List thành hai phần (< pivot và > pivot), sau đó đệ quy.
def quick_sort(lst):
if len(lst) <= 1:
return lst
pivot = lst[len(lst) // 2]
left = [x for x in lst if x < pivot]
middle = [x for x in lst if x == pivot]
right = [x for x in lst if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
print(quick_sort([10, 7, 8, 9, 1, 5]))
# Output: [1, 5, 7, 8, 9, 10]
Độ phức tạp:
- Trung bình: O(n log n).
- Tệ nhất: O(n²) (pivot không tốt).
- Không stable.
4. So sánh các thuật toán sắp xếp
| Algorithm | Average Time | Worst Time | Space | Stable? |
|---|---|---|---|---|
| Bubble Sort | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(1) | No |
| Insertion Sort | O(n²) | O(n²) | O(1) | Yes |
| Quick Sort | O(n log n) | O(n²) | O(log n) | No |
| Python Timsort | O(n log n) | O(n log n) | O(n) | Yes |
5. Tùy biến việc sắp xếp List
Bạn có thể dùng key để sắp xếp List theo tiêu chí riêng.
Ví dụ: Sắp xếp danh sách sinh viên theo điểm giảm dần, nếu điểm bằng nhau thì theo tên tăng dần
students = [
{"name": "Alice", "score": 90},
{"name": "Bob", "score": 85},
{"name": "Charlie", "score": 90}
]
sorted_students = sorted(
students,
key=lambda s: (-s["score"], s["name"])
)
print(sorted_students)
# Output: [{'name': 'Alice', 'score': 90},
# {'name': 'Charlie', 'score': 90},
# {'name': 'Bob', 'score': 85}]6. Những sai lầm thường gặp khi sắp xếp List
- Nhầm
list.sort()vớisorted(). - Quên rằng
list.sort()trả vềNone. - Gán tham chiếu thay vì copy khi cần giữ dữ liệu gốc.
- Không cân nhắc ổn định (stable) khi dữ liệu phức tạp.
- Dùng thuật toán O(n²) cho List lớn gây chậm trễ.
7. Ứng dụng thực tế của Sorting trên List
- Tìm kiếm nhị phân: yêu cầu List đã sắp.
- Phân tích dữ liệu: xếp hạng, thống kê.
- Game & AI: sắp thứ tự đối thủ, sắp sự kiện.
- UX: hiển thị dữ liệu theo tiêu chí mong muốn.
8. Kết luận
Qua bài viết này, mình đã đi từ cơ bản đến nâng cao:
- Dùng hàm dựng sẵn (
sort,sorted) để sắp xếp nhanh và hiệu quả. - Hiểu các thuật toán cơ bản như Bubble, Selection, Insertion, Quick Sort.
- Biết cách tùy biến việc sắp xếp List với
key. - Nhận diện sai lầm thường gặp và cách tránh.
Nếu bạn làm việc với Python hàng ngày, hãy tận dụng sort() và sorted() vì hiệu suất cao và an toàn. Nhưng cũng đừng bỏ qua việc luyện tập thuật toán thủ công — đây là cách để hiểu cặn kẽ hơn về cách máy tính làm việc.
9. Tài liệu tham khảo
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
- Python Software Foundation. (2025). Sorting HOW TO. Python 3 Documentation. Retrieved from https://docs.python.org/3/howto/sorting.html
- GeeksforGeeks. (2025). Sorting Algorithms. Retrieved from https://www.geeksforgeeks.org/sorting-algorithms/
