0

Thuật toán & CTDL #02: Selection Sort - mảng đã sắp sẵn mà vẫn chạy đủ 28 lần so sánh

Selection Sort có một tính cách khá khó chịu: kể cả khi mảng đã sắp xếp sẵn, nó vẫn so sánh y như cũ. Không dừng sớm, không tận dụng được gì. Nhưng nó cũng có một điểm mạnh ít thuật toán nào có: số lần đổi chỗ cực ít. Bài này đi qua cả hai mặt đó, và một câu hỏi phỏng vấn rất hay gặp: Selection Sort có stable không?

Ý tưởng

Chia mảng thành hai phần: bên trái là phần đã sắp, bên phải là phần chưa sắp. Mỗi lượt:

  1. Quét hết phần chưa sắp để tìm phần tử nhỏ nhất.
  2. Đổi chỗ nó với phần tử đầu tiên của phần chưa sắp, bằng đúng một lần đổi chỗ.

Phần đã sắp lớn dần từ trái sang phải, mỗi lượt thêm một ô. Sau n-1 lượt, mảng được sắp xong (phần tử cuối cùng tự động đúng chỗ).

Chạy tay một ví dụ

Mảng trong video: [5, 2, 8, 1, 7, 3, 6, 4].

Lượt Quét (số so sánh) Nhỏ nhất Mảng sau lượt
1 7 1 [1, 2, 8, 5, 7, 3, 6, 4]
2 6 2 (đã đúng chỗ) [1, 2, 8, 5, 7, 3, 6, 4]
3 5 3 [1, 2, 3, 5, 7, 8, 6, 4]
4 4 4 [1, 2, 3, 4, 7, 8, 6, 5]
5 3 5 [1, 2, 3, 4, 5, 8, 6, 7]
6 2 6 [1, 2, 3, 4, 5, 6, 8, 7]
7 1 7 [1, 2, 3, 4, 5, 6, 7, 8]

Nhìn lượt 2: số 2 đã đứng đúng chỗ từ đầu, vậy mà thuật toán vẫn phải quét hết 6 ô còn lại mới dám chắc nó là nhỏ nhất. Không có cách nào biết trước.

Tổng: 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 lần so sánh, nhưng chỉ 6 lần đổi chỗ (lượt 2 không cần đổi).

Đưa cho nó mảng đã sắp sẵn [1, 2, ..., 8]? Vẫn đúng 28 lần so sánh, chỉ khác là 0 lần đổi chỗ.

Code Python

def selection_sort(a):
    a = list(a)
    n = len(a)
    for i in range(n - 1):
        m = i                            # vị trí nhỏ nhất tạm thời
        for j in range(i + 1, n):        # luôn quét hết, không dừng sớm được
            if a[j] < a[m]:
                m = j
        if m != i:                       # tối đa 1 lần đổi chỗ mỗi lượt
            a[i], a[m] = a[m], a[i]
    return a

print(selection_sort([5, 2, 8, 1, 7, 3, 6, 4]))  # [1, 2, 3, 4, 5, 6, 7, 8]
print(selection_sort([3]))                       # [3]

Độ phức tạp

  • Số so sánh: luôn đúng n(n-1)/2, không phụ thuộc dữ liệu. Tốt nhất, trung bình, tệ nhất đều O(n²).
  • Số lần đổi chỗ: tối đa n-1, tức O(n). Đây là điểm khác biệt lớn nhất so với Bubble Sort (có thể tới n(n-1)/2 lần đổi chỗ) và Insertion Sort (có thể tới O(n²) lần dịch phần tử).
  • Bộ nhớ: O(1), in-place.
  • Stable: không (với cách cài đặt đổi chỗ như trên).

Vì sao không stable?

Lấy mảng [2a, 2b, 1], trong đó 2a và 2b có cùng giá trị 2. Lượt 1 tìm được nhỏ nhất là 1, đổi chỗ với 2a:

[2a, 2b, 1]  ->  [1, 2b, 2a]

2a vừa bị "nhảy cóc" qua 2b. Thứ tự ban đầu của hai phần tử bằng nhau đã bị đảo. Phép đổi chỗ đường dài chính là thứ làm Selection Sort vừa ít ghi bộ nhớ, vừa mất tính stable.

Có thể làm nó stable bằng cách thay vì đổi chỗ, ta lấy phần tử nhỏ nhất ra rồi dịch cả đoạn sang phải một ô để chèn vào. Nhưng khi đó số lần ghi lại thành O(n²), mất luôn điểm mạnh duy nhất.

Khi nào dùng, khi nào không

Lợi thế thật sự của Selection Sort là ít ghi. Nó hữu ích khi:

  • Ghi bộ nhớ đắt hơn đọc rất nhiều, ví dụ bộ nhớ flash/EEPROM có giới hạn số lần ghi.
  • Mỗi phần tử rất to và đổi chỗ tốn kém (dù trong thực tế người ta thường sắp mảng con trỏ/chỉ số thay vì di chuyển dữ liệu thật).
  • Mảng rất nhỏ và bạn cần code đơn giản, dễ kiểm chứng.

Không nên dùng khi dữ liệu thường đã gần sắp xếp (Insertion Sort tận dụng được, Selection Sort thì không), khi cần stable, hoặc đơn giản là khi dữ liệu lớn.

Một ý tưởng thú vị: nếu thay bước "quét tìm nhỏ nhất" O(n) bằng một cấu trúc dữ liệu lấy được nhỏ nhất trong O(log n), bạn sẽ có Heap Sort, O(n log n). Về bản chất, Heap Sort là Selection Sort được tăng tốc.

Lỗi hay gặp

  1. Đổi chỗ ngay trong vòng trong mỗi khi thấy số nhỏ hơn. Code vẫn ra kết quả đúng nhưng số lần đổi chỗ thành O(n²), mất luôn lý do để chọn Selection Sort.
  2. Lưu giá trị thay vì vị trí của phần tử nhỏ nhất, đến lúc đổi chỗ không biết nó nằm ở đâu.
  3. Nghĩ rằng mảng đã sắp thì chạy nhanh hơn. Không, số so sánh luôn như nhau.

Câu hỏi phỏng vấn hay gặp

  • Vì sao Selection Sort ít ghi bộ nhớ nhất trong nhóm sort O(n²) cơ bản? Vì mỗi lượt chỉ đổi chỗ tối đa một lần, tổng tối đa n-1 lần.
  • Selection Sort có stable không? Không, do phép đổi chỗ đường dài. Ví dụ [2a, 2b, 1].
  • Có dừng sớm được như Bubble Sort không? Không. Muốn biết phần tử nào nhỏ nhất thì bắt buộc phải xem hết phần còn lại.

Lời kết

Selection Sort dạy một điều quan trọng: "nhanh" không chỉ có một thước đo. Cùng là O(n²) so sánh, nhưng số lần ghi có thể chênh nhau cả bậc, và tùy phần cứng mà cái nào đắt hơn sẽ khác.

Đây là bài 02/19 của series "Thuật toán & Cấu trúc dữ liệu - Giải thuật". Bản video ngắn có hoạt hình minh họa từng lượt "đi tìm số nhỏ nhất" nằm trên page Trà Đá Tech: https://www.facebook.com/profile.php?id=61596642752252

Bạn đã gặp tình huống nào mà chi phí ghi quan trọng hơn chi phí đọc chưa? Hãy chia sẻ trong phần bình luận.

Nếu thấy bài viết hữu ích, hãy upvote và follow để theo dõi các bài tiếp theo.

Bài tiếp theo: Insertion Sort - thuật toán xếp bài mà các thư viện sort xịn vẫn dùng cho mảng nhỏ


All rights reserved

Viblo
Hãy đăng ký một tài khoản Viblo để nhận được nhiều bài viết thú vị hơn.
Đăng kí