Selection Sort là một thuật toán sắp xếp tương đối dễ hiểu. Ý tưởng chính vẫn là đổi chỗ những cặp nghịch thế, tuy nhiên cái hay là ở chỗ Selection Sort tìm vị trí chứa phần tử nhỏ nhất để đổi chỗ với phần tử đang xét chứ không đổi tất cả các cặp nghịch thế như Bubble Sort hay Interchange Sort.

Ý tưởng

Xét phần tử đầu tiên của dãy. Tìm phần tử nhỏ nhất trong các phần tử còn lại. Hoán đổi phần tử đầu tiên với phần tử nhỏ nhất này, ta được phần tử đầu tiên có vị trí đúng. Bỏ qua phần tử vừa được xét, tiếp tục xét đến phần tử kế tiếp và thực hiện đến hết dãy.

Cài đặt trong C++

int min, i, j; //min là chỉ số phần tử nhỏ nhất
for(i = 0; i < n-1; i++)
{
   min = i;
   for(j = i+1; j < n; j++)
      if(a[j] < a[min])
         min = j; //tìm min trong các phần tử còn lại
   if(min != i)
     swap(a[i], a[min]); //đổi chỗ nếu tìm thấy min
}

Minh họa

Nguồn: Wikipedia.

Minh họa Selection Sort

Đánh giá

Về số phép so sánh, ở lượt xét thứ i luôn có n-i phép so sánh để tìm min và không phụ thuộc tình trạng ban đầu của dãy nên số phép so sánh ước lượng là: $(n-1) + (n-2) + … + 1 = n(n - 1)/2$.

Số lần hoán vị ở trường hợp tốt nhất là $0$. Trường hợp xấu nhất là: $3n(n-1)/2$.

Độ phức tạp là: $O(n^2)$.