DAA — выбор сортировки

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

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 , выполняется точно одинаковое количество раз в каждом случае.

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

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

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

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

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

Для каждого i от 1 до n — 1 существует один обмен и n — i сравнений, таким образом, имеется в общей сложности n — 1 обменов и

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

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

В худшем случае это может быть квадратично, но в среднем это количество равно O (n log n) . Это означает, что время выполнения сортировки Selection довольно нечувствительно к вводу .

Реализация

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

пример

Несортированный список:

1- ^я итерация:

Наименьший = 5

2 <5, самый маленький = 2

1 <2, самый маленький = 1

4> 1, наименьшее = 1

3> 1, наименьшее = 1

Поменяйте местами 5 и 1

2- ^я итерация:

Наименьший = 2

2 <5, самый маленький = 2

2 <4, самый маленький = 2

2 <3, самый маленький = 2

Нет своп

3- ^я итерация:

Наименьший = 5

4 <5, самый маленький = 4

3 <4, самый маленький = 3

Поменяйте местами 5 и 3

4- ^я итерация:

Наименьший = 4

4 <5, самый маленький = 4

Нет своп

В заключение,

отсортированный список