DAA - Выборочная сортировка

Такой вид сортировки называется Selection Sortпоскольку он работает путем многократной сортировки элементов. Он работает следующим образом: сначала найдите наименьший элемент в массиве и замените его элементом в первой позиции, затем найдите второй наименьший элемент и замените его элементом во второй позиции, и продолжайте таким образом, пока весь массив не будет отсортировано.

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

Сортировка по выбору - один из самых простых способов сортировки, и он очень хорошо работает для небольших файлов. Это очень важное приложение, поскольку каждый элемент фактически перемещается не более одного раза.

Сортировка разделов - это предпочтительный метод сортировки файлов с очень большими объектами (записями) и маленькими ключами. Худший случай возникает, если массив уже отсортирован в порядке убывания, а мы хотим отсортировать их в порядке возрастания.

Тем не менее, время, необходимое для алгоритма сортировки выбора, не очень чувствительно к исходному порядку сортировки массива: проверка, если A[j] < min x во всех случаях выполняется одинаковое количество раз.

Сортировка выбора тратит большую часть своего времени на поиск минимального элемента в неотсортированной части массива. Это ясно показывает сходство между сортировкой по выбору и сортировкой по пузырькам.

Сортировка пузырьков выбирает максимальное количество оставшихся элементов на каждом этапе, но тратит некоторые усилия на упорядочение несортированной части массива.
Сортировка выбора является квадратичной как в худшем, так и в среднем случае и не требует дополнительной памяти.

Для каждого i из 1 к n - 1, есть одна биржа и n - i сравнений, так что всего n - 1 обмены и

(n − 1) + (n − 2) + ...+ 2 + 1 = n(n − 1)/2 сравнения.

Эти наблюдения верны независимо от входных данных.

В худшем случае это могло быть квадратичным, но в среднем случае эта величина равна O(n log n). Это означает, чтоrunning time of Selection sort is quite insensitive to the input.

Реализация

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; 
   } 
}