Array (mảng) là cấu trúc dữ liệu nền tảng trong lập trình — lưu trữ nhiều phần tử theo thứ tự, cho phép truy cập nhanh theo chỉ số. Việc sắp xếp các phần tử trong Array là thao tác cực kỳ phổ biến và quan trọng: giúp tìm kiếm nhanh hơn (ví dụ binary search), dễ phân tích hay trình bày dữ liệu (ví dụ sắp xếp theo điểm, theo tên). Trong bài này, mình sẽ đi từ tổng quan đến thực hành: dùng hàm có sẵn và tự hiện thực các thuật toán, phân tích độ phức tạp và nêu những lưu ý thực tế.
1. Tổng quan về Array và Sorting
Array là một tập hợp các phần tử lưu liên tiếp trong bộ nhớ (ở nhiều ngôn ngữ). Việc sắp xếp (sorting) đưa các phần tử về một thứ tự xác định — thường là tăng dần hoặc giảm dần, nhưng cũng có thể là theo tiêu chí tùy biến (ví dụ: độ dài chuỗi, số điểm).
Tại sao cần sắp xếp?
- Tăng tốc tìm kiếm (binary search yêu cầu dữ liệu đã sắp).
- Chuẩn hóa hiển thị (danh sách theo tên, theo điểm).
- Hỗ trợ các thuật toán khác (merge step trong merge sort, kỹ thuật two-pointer, …).
Loại sắp xếp cơ bản:
- In-place (sắp ngay trên mảng, không cần bộ nhớ phụ lớn).
- Not in-place (trả về mảng mới).
- Stable (giữ thứ tự tương đối của phần tử bằng nhau) vs Unstable.
2. Sắp xếp Array bằng hàm dựng sẵn
Trong Python có hai cách chính: sorted() (trả về list mới) và list.sort() (sắp xếp tại chỗ).
Ví dụ và giải thích (code comments bằng tiếng Anh):
numbers = [5, 2, 9, 1, 5]
# Returns a new sorted list
sorted_numbers = sorted(numbers) # returns a new sorted list
# Sorts the list in-place (no new list created)
numbers.sort() # sorts the list in-place
# Sorting with a custom key: sort strings by length
words = ["apple", "fig", "banana"]
words.sort(key=len) # sorts by the length of each string
Giải thích chi tiết:
sorted()trả về một danh sách mới, phù hợp khi bạn cần giữ mảng gốc.list.sort()nhanh hơn chút vì làm trực tiếp (in-place) và không tạo bản sao.- Cả hai chấp nhận tham số
key=để định nghĩa tiêu chí sắp xếp (ví dụkey=lenhoặckey=lambda x: x['score']) vàreverse=Trueđể sắp giảm dần. - Python dùng thuật toán Timsort (kết hợp insertion + merge), hiệu quả cho dữ liệu thực tế — O(n log n) trung bình, stable.
Ưu điểm của hàm dựng sẵn: nhanh, an toàn, chuẩn; nhược điểm: ít kiểm soát chi tiết thuật toán (nhưng điều này hiếm khi cần).
3. Các thuật toán sắp xếp phổ biến
Dưới đây mình triển khai bốn thuật toán tiêu biểu, có code Python (comment & biến bằng English) và giải thích chi tiết từng bước, độ phức tạp, khi nào hợp lý dùng.
3.1 Bubble Sort
Ý tưởng: Lặp qua mảng, so sánh từng cặp kế nhau và hoán đổi nếu sai thứ tự; lặp cho đến khi không còn hoán đổi.
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
# If the element found is greater than the next element, swap them
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
# If no two elements were swapped by inner loop, then break
if not swapped:
break
return arr
Giải thích chi tiết:
- Vòng ngoài chạy
nlần, vòng trong đưa phần tử lớn nhất còn lại về cuối. swappedgiúp tối ưu: nếu vòng trong không hoán đổi nào — mảng đã sắp — ta dừng sớm.- Độ phức tạp: O(n²) thời gian (tệ nhất & trung bình), O(1) không gian.
- Khi dùng? Chỉ dùng để học thuật, demo vì đơn giản; không dùng cho dữ liệu lớn.
3.2 Selection Sort
Ý tưởng: Với mỗi vị trí i, tìm phần tử nhỏ nhất từ i..n-1 và đổi chỗ vào vị trí i.
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
# Swap the found minimum element with the first element
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
Giải thích:
- Mỗi lần chọn phần tử nhỏ nhất và đặt vào vị trí tiếp theo.
- Độ phức tạp: O(n²), không gian O(1).
- Không stable nếu triển khai hoán đổi trực tiếp (có cách stable hơn nhưng phức tạp hơn).
- Thường dùng cho học thuật hoặc khi bộ nhớ phụ bị hạn chế nhưng vẫn không phải lựa chọn tốt cho n lớn.
3.3 Insertion Sort
Ý tưởng: Xây dãy đã sắp xếp từ đầu, lần lượt chèn từng phần tử mới vào vị trí phù hợp.
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
# Move elements of arr[0..i-1] that are greater than key to one position ahead
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
Giải thích:
- Hiệu quả với mảng gần như đã sắp xếp: thời gian gần O(n).
- Độ phức tạp trung bình & tệ nhất O(n²), bộ nhớ O(1).
- Stable (bảo toàn thứ tự tương đối phần tử bằng nhau).
- Thường dùng cho mảng nhỏ hoặc như một bước trong thuật toán phức tạp hơn (ví dụ trong Timsort).
3.4 Quick Sort
Ý tưởng: Chọn một pivot, chia mảng thành hai phần (< pivot và >= pivot), đệ quy sắp xếp hai phần rồi ghép lại.
def quick_sort(arr):
# Base case
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
# Recursively sort left and right, then concatenate
return quick_sort(left) + middle + quick_sort(right)
Giải thích chi tiết:
- Cách triển khai trên là version không in-place, dễ hiểu (sử dụng list comprehensions).
- Độ phức tạp trung bình O(n log n), tệ nhất O(n²) (khi pivot tệ — ví dụ khi mảng đã sắp theo thứ tự và pivot luôn là phần tử cực đoan).
- Không stable theo triển khai này; có thể làm in-place với partition (Lomuto/Hoare) để giảm bộ nhớ.
- Thường chọn pivot ngẫu nhiên hoặc median-of-three để cải thiện trường hợp xấu.
- Quick Sort rất phổ biến nhờ hiệu năng tốt trung bình và thường nhanh hơn merge sort ở bộ nhớ cache.
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 (simple) |
| 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(n) (naive) / O(log n) (in-place) | No (typical) |
| Python Timsort (built-in) | O(n log n) | O(n log n) | O(n) | Yes |
Khi nào dùng:
- Dùng hàm dựng sẵn cho hầu hết trường hợp (hiệu suất và ổn định tốt).
- Dùng Insertion cho mảng nhỏ hoặc gần sắp xếp.
- Dùng Quick khi cần thuật toán nhanh trung bình, triển khai attention đến pivot.
- Bubble / Selection chủ yếu cho mục đích học.
5. Tùy biến việc sắp xếp
Trong thực tế ta hay cần sắp xếp theo tiêu chí riêng (ví dụ: sắp theo điểm, ưu tiên điểm cao, hoặc sắp strings theo độ dài).
Ví dụ: sắp 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": 85},
{"name": "Bob", "score": 92},
{"name": "Charlie", "score": 85}
]
# Sort by score descending, then name ascending
sorted_students = sorted(
students,
key=lambda s: (-s["score"], s["name"])
)
Giải thích: key trả về một tuple (-score, name). Việc dùng -score đảo chiều để sắp giảm dần theo điểm; thứ tự tiếp theo là name tăng dần.
6. Những sai lầm thường gặp khi sắp xếp Array
- Nhầm lẫn
sorted()vàlist.sort()dẫn đến việc vô tình sửa mảng gốc. - Quên là
sort()trả vềNone(vì thao tác in-place) — nên không gánx = list.sort(). - Quên copy mảng khi cần giữ dữ liệu gốc:
new = sorted(old)thay vìnew = old(chỉ gán tham chiếu). - Không xét đến ổn định khi sắp xếp dữ liệu phức tạp (cần stable để bảo toàn tiêu chí phụ).
- Sử dụng thuật toán O(n²) cho dataset lớn dẫn đến thời gian rất chậm.
7. Ứng dụng thực tế của Sorting trong lập trình
- Binary Search: chỉ áp dụng khi dữ liệu đã sắp xếp.
- Xử lý dữ liệu: thống kê, tính ranking, top-k.
- Chuỗi thao tác trong thuật toán phức tạp: merge step (merge sort), sweep-line algorithms, two-pointer techniques.
- Giao diện và UX: sắp xếp danh sách theo tên/ngày/điểm giúp người dùng nhanh tìm thông tin.
8. Kết luận
Sắp xếp Array là kỹ năng cơ bản nhưng cực kỳ quan trọng trong lập trình. Mình khuyến khích:
- Dùng hàm dựng sẵn (
sorted,list.sort()) trong phần lớn trường hợp để đạt hiệu năng và độ ổn định tốt. - Tự triển khai và hiểu các thuật toán: Bubble, Selection, Insertion, Quick để nắm rõ bản chất time/space trade-off.
- Biết khi nào cần tối ưu: nếu dataset lớn, chọn thuật toán O(n log n) ổn định và chú ý bộ nhớ; nếu mảng gần sắp xếp, Insertion rất hiệu quả.
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/
