DAA - Sắp xếp lựa chọn

Kiểu sắp xếp này được gọi là Selection Sortvì nó hoạt động bằng cách sắp xếp nhiều lần các phần tử. Nó hoạt động như sau: đầu tiên tìm phần tử nhỏ nhất trong mảng và trao đổi nó với phần tử ở vị trí đầu tiên, sau đó tìm phần tử nhỏ nhất thứ hai và trao đổi nó với phần tử ở vị trí thứ hai và tiếp tục theo cách này cho đến khi toàn bộ mảng đã sắp xếp.

Algorithm: Selection-Sort (A) 
fori ← 1 to n-1 do 
   min j ← i; 
   min x ← A[i] 
   for j ←i + 1 to n do 
      if A[j] < min x then 
         min j ← j 
         min x ← A[j] 
   A[min j] ← A [i] 
   A[i] ← min x

Sắp xếp lựa chọn là một trong những kỹ thuật sắp xếp đơn giản nhất và nó hoạt động rất tốt đối với các tệp nhỏ. Nó có một ứng dụng khá quan trọng là mỗi mục thực sự được di chuyển nhiều nhất một lần.

Sắp xếp theo phần là một phương pháp được lựa chọn để sắp xếp các tệp có các đối tượng rất lớn (bản ghi) và các khóa nhỏ. Trường hợp xấu nhất xảy ra nếu mảng đã được sắp xếp theo thứ tự giảm dần và chúng ta muốn sắp xếp chúng theo thứ tự tăng dần.

Tuy nhiên, thời gian theo yêu cầu của thuật toán sắp xếp lựa chọn không nhạy cảm lắm với thứ tự ban đầu của mảng được sắp xếp: kiểm tra nếu A[j] < min x được thực hiện chính xác cùng một số lần trong mọi trường hợp.

Sắp xếp lựa chọn dành phần lớn thời gian để cố gắng tìm phần tử tối thiểu trong phần không được sắp xếp của mảng. Nó cho thấy rõ ràng sự giống nhau giữa sắp xếp Lựa chọn và Sắp xếp bong bóng.

Sắp xếp bong bóng chọn các phần tử còn lại tối đa ở mỗi giai đoạn, nhưng lãng phí một số nỗ lực đưa ra một số thứ tự cho một phần không được sắp xếp của mảng.
Sắp xếp lựa chọn là bậc hai trong cả trường hợp xấu nhất và trung bình và không yêu cầu thêm bộ nhớ.

Cho mỗi i từ 1 đến n - 1, có một cuộc trao đổi và n - i so sánh, vì vậy có tổng số n - 1 trao đổi và

(n − 1) + (n − 2) + ...+ 2 + 1 = n(n − 1)/2 so sánh.

Những quan sát này giữ nguyên, bất kể dữ liệu đầu vào là gì.

Trong trường hợp xấu nhất, điều này có thể là bậc hai, nhưng trong trường hợp trung bình, đại lượng này là O(n log n). Nó ngụ ý rằngrunning time of Selection sort is quite insensitive to the input.

Thực hiện

Void Selection-Sort(int numbers[], int array_size) { 
   int i, j; 
   int min, temp;  
   for (i = 0; I < array_size-1; i++) { 
      min = i; 
      for (j = i+1; j < array_size; j++) 
         if (numbers[j] < numbers[min]) 
            min = j; 
      temp = numbers[i]; 
      numbers[i] = numbers[min]; 
      numbers[min] = temp; 
   } 
}