Algorithm: Thuật toán sắp xếp chọn (selection sort)

Hình động sắp xếp chọn

Từ cái tên của thuật toán ta có thể đoán ngay được ý tưởng của thuật toán. Thật đúng như vậy, giả sử chúng ta muốn sắp xếp một danh sách (mảng) theo chiều tăng dần thì rõ ràng phần tử đầu tiên của danh sách sẽ là phần tử nhỏ nhất, phần tử tiếp theo là phần tử nhỏ thứ 2, tiếp nữa là phần tử nhỏ thứ 3,... đến hết. Như vậy, ta xét từng vị trí và chọn phần tử tương ứng với vị trí đó.

Có thể thấy ngay, ở vị trí 1 ta sẽ chọn phần tử nhỏ nhất của danh sách và đổi chỗ với phần tử đó với phần tử ở vị trí 1. Như vậy, sau bước đầu tiên này, phần tử nhỏ nhất đã vào vị trí. Ta lại tiếp tục xét vị trí tiếp theo (vị trí 2), lúc này ta sẽ chọn phần tử nhỏ thứ 2 của danh sách để đổi chỗ với phần tử ở vị trí 2 này. Vì phần tử 1 đã vào đúng vị trí nên thực tế ta không cần quan tâm đến nó nữa, có nghĩa là phần tử nhỏ thứ 2 cũng chính là phần tử nhỏ nhất trong các phần tử còn lại. Ta đi tìm phần tử nhỏ nhất trong các phần tử còn lại và đổi chỗ cho phần tử ở vị trí thứ 2, cứ thế ta sẽ thực hiện đến vị trí thứ n-1 thì danh sách sẽ được sắp xếp.

Hãy xem ví dụ sau:

a=[3, 6, 9, 2, 6, 8, 9, 1, 7, 21, 7, 12]

Ta sẽ thực hiện thuật toán sắp xếp chọn với ví dụ trên như sau:

1. Từ phần tử đầu tiên (có giá trị 3) so sánh với giá trị thứ 2 (có giá trị là 6), ta thấy 3 và 6 đúng thứ tự không làm gì cả.
2. Lại thấy phần tử đầu tiền (có giá trị là 3) và  phần tử thứ 3 (có giá trị là 9) đúng thứ tự ta không làm gì và chuyển bước tiếp theo.
3. Thấy phần tử thứ nhất (3) và phần tử thứ tư (2) sai thứ tự, như vậy ta sẽ đổi chỗ phần tử thứ nhất và thứ tư. Danh sách a lúc này như sau:
   a=[2, 6, 9, 3, 6, 8, 9, 1, 7, 21, 7, 12]
4. Tiếp tục, phần tử thứ nhất (có giá trị 2) và phần tử thứ năm (có giá trị 6) đúng thứ tự, chuyển bước tiếp theo.
5. Bước tiếp, phần tử đầu tiên (2) và phần tử thứ sáu (8) đúng thứ tự, chuyển bước tiếp theo.
6. Phần tử thứ nhất (2) và phần tử thứ bảy (9) đúng thứ tự không làm gì và chuyển bước tiếp.
7. Phần tử thứ nhất (2) và phần tử thứ tám (có giá trị 1) sai thứ tự, nên ta đổi chỗ hai phần tử này. Sau khi đổi chỗ ta được:
   a=[1, 6, 9, 3, 6, 8, 9, 2, 7, 21, 7, 12]
8. Xét phần tử đầu tiên (lúc này có giá trị 1) và phần tử thứ chín (có giá trị 7) đúng thứ tự nên ta chuyển bước tiếp.
9. So sánh phần tử thứ nhất (1) và phần tử thứ mười (21) thấy đúng thứ tự nên chuyển bước sau.
10. Lại thấy phần tử đầu tiên (1) và phần tử thứ 11 (7) đúng thứ tự nên ta tiếp tục bước so sánh tiếp theo.
11. Lúc này, phần tử thứ nhất (1) và phần tử cuối dãy (12) đúng thứ tự nên ta không phải đổi chỗ. Kết thúc vòng lặp thứ nhất, phần tử nhỏ nhất của danh sách đã được chọn và đặt vào vị trí đầu dãy.
12. Lúc này, vị trí nhỏ nhất được đặt vào vị trí đầu tiên, chính vì vậy, vị trí thứ hai sẽ lưu trữ phần tử nhỏ thứ hai, hay nói cách khác là phần tử nhỏ nhất trong các phần tử còn lại. Lúc này, ta hãy coi như không có phần tử thứ nhất và thực hiện các bước trên với mảng mới:
    a'=[6, 9, 3, 6, 8, 9, 2, 7, 21, 7, 12]

Bằng việc chọn phần tử nhỏ nhất và đặt vào vị trí "thích hợp" như trên, sau n-1 lần lặp ta sẽ được một danh sách được sắp xếp theo thứ tự tăng dần.

Python code:

C code (phiên bản sử dụng con trỏ):

Với cách làm như trên, có thể thấy là thao tác đổi chỗ được thực hiện rất nhiều lần (từ bước 1 đến bước 11 ta đổi chỗ hai lần 3 vs 2 và 2 vs 1). Trong các vòng lặp khác nữa, ta lại thực hiện đổi chỗ rất nhiều lần. Vậy liệu việc đổi chỗ nhiều có ảnh hưởng tới thời gian thực hiện thuật toán không? Câu trả lời là tùy thuộc vào cấu trúc dữ liệu để lưu trữ các phần tử, nếu sử dụng các cấu trúc dễ dàng đổi vị trí thì không có ảnh hưởng gì cả. Còn những cấu trúc và việc tráo đổi vị trí không dễ dành (danh sách móc nối chẳng hạn) thì sẽ ảnh hưởng tới thời gian thực hiện. Vậy, có cách nào để hạn chế việc đổi chỗ không? Có một cách như thế này, ta sẽ dùng 2 biến là t và k. Đầu tiên, tại mỗi vòng lặp ta gán t bằng giá trị của vị trí cần chọn phần tử nhỏ nhất để đặt vào và k chính là chỉ số của vị trí trên. Ta xét các phần tử từ k+1 đến cuối dãy, nếu phần tử có phần tử j (k+1 ≤ j < độ dài danh sách) thì ta gán t = a[j] và k=j. Hết vòng lặp, nếu k thay đổi thì ta sẽ đổi chỗ hai phần tử a[k] và phần tử đang chọn giá trị nhỏ nhất cho nhau.
Như vậy, với cách làm thứ hai thì chỉ có tối đa một lần đổi chỗ được thực hiện trong mỗi vòng lặp. Sau đây là code cho cách làm này:
Python code:
C code (phiên bản sử dụng con trỏ):

Bạn có thể tải code đầy đủ tại đây (python, c).