Thuật toán sắp xếp chọn trực tiếp (Selection Sort)

[Demo Đồ họa] Thuật toán sắp xếp

1. Bài toán
Cho dãy X = {X1, X1, ..., Xn}, hãy sắp xếp dãy theo chiều không giảm.

2. Ý tưởng

Chọn phần tử nhỏ nhất trong n phần tử ban đầu, đưa phần tử này về vị trí đúng là đầu tiên của dãy hiện hành. Sau đó không quan tâm đến nó nữa, xem dãy hiện hành chỉ còn n-1 phần tử của dãy ban đầu, bắt đầu từ vị trí thứ 2. Lặp lại quá trình trên cho dãy hiện hành đến khi dãy hiện hành chỉ còn 1 phần tử.

Do dãy ban đầu có n phần tử, vậy tóm tắt ý tưởng thuật toán là thực hiện n-1 lượt việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đúng ở đầu dãy.

3. Giải thuật
- Bước 1: i = 1;
- Bước 2: Tìm X[min] trong dãy X[i] ... X[n]
- Bước 3: Đỗi chổ X[i] cho X[min], nếu min trùng với i thì bỏ qua bước này.
- Bước 4:
* Nếu i <= n-1 thì tăng i lên 1 vị trí (i = i +1), quay lại Bước 2.
* Ngược lại, dừng, dãy đã cho đã sắp xếp đung vị trí.

4. Mã ngôn ngữ C

void SelectionSort(int X[], int n)
{
  int min;
  for(int i=0;i<n-1;i++)
  {
      min=i;
      for(int j=i+1;j<n;j++)
        if(X[j]<X[min]) min=j;  // Tìm được vị trí chứa giá trị nhỏ nhất
      swap(a[min],a[i]);        // Đổi chổ min cho i
  }
}

5. Ví dụ
X = {7, 2, 5, 4, 1, 3, 8, 6}
Dãy ban đầu 7, 2, 5, 4, 1, 3, 8, 6
i=1, min=5, swap(X[min],X[i]) ta có 1, 2, 5, 4, 7, 3, 8, 6
i=2, min=2, không đổi chổ ta có 1, 2, 5, 4, 7, 3, 8, 6
i=3, min=5, swap(X[min],X[i]) ta có 1, 2, 3, 4, 7, 5, 8, 6
i=4, min=4, không đổi chổ ta có 1, 2, 3, 4, 7, 5, 8, 6
i=5, min=6, swap(X[min],X[i]) ta có 1, 2, 3, 4, 5, 7, 8, 6
i=6, min=8, swap(X[min],X[i]) ta có 1, 2, 3, 4, 5, 6, 8, 7
i=7, min=8, swap(X[min],X[i]) ta có 1, 2, 3, 4, 5, 6, 7, 8 (dãy đã sắp xếp)

6. Đánh giá giải thuật

Đối với giải thuật chọn trực tiếp, có thể thấy rằng ở lượt thứ i, bao giờ cũng cần (n-i) lần so sánh để xác định phần tử nhỏ nhất hiện hành. Số lượng phép so sánh này không phụ thuộc vào tình trạng của dãy số ban đầu, do vậy trong mọi trường hợp có thể kết luận:

Số lần hoán vị ( một hoán vị bằng 3 phép gán) lại phụ thuộc vào tình trạng ban đầu của dãy số, ta chỉ có thể ước lượng trong từng trường hợp sau:

Thuật toán ít phải đổi chỗ các phần tử nhất trong số các thuật toán sắp xếp(n lần hoán vị) nhưng có độ phức tạp so sánh là O(n2) (n2/2 phép so sánh).
Thuật toán tốn thời gian gần như bằng nhau đối với mảng đã được sắp xếp cũng như mảng chưa được sắp xếp.
Insertion Sort và Selection Sort đều có chi phí cho trường hợp xấu nhất là O(n^2).
Insertion Sort tốt hơn Selection Sort nhất là khi mảng đã có thứ tự sẵn.


Các thuật toán sắp xếp khác:

   [Thuật toán đang xem] Selection Sort

   [Thuật toán sắp xếp] Insertion Sort + Binary Insertion Sort

   [Thuật toán sắp xếp] Interchange Sort

   [Thuật toán sắp xếp] Bubble Sort

   [Thuật toán sắp xếp] Quick Sort