Учебники

Сортировка структуры данных и алгоритмов

Сортировка выбора – это простой алгоритм сортировки. Этот алгоритм сортировки представляет собой алгоритм сравнения на месте, в котором список делится на две части: отсортированная часть на левом конце и несортированная часть на правом конце. Изначально отсортированная часть пуста, а несортированная часть – весь список.

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

Этот алгоритм не подходит для больших наборов данных, поскольку его средняя и наихудшая сложности имеют значение of (n 2 ), где n – количество элементов.

Как работает сортировка выбора?

Рассмотрим следующий изображенный массив в качестве примера.

Несортированный массив

Для первой позиции в отсортированном списке весь список сканируется последовательно. Первая позиция, где в настоящее время хранится 14, мы ищем по всему списку и находим, что 10 является самым низким значением.

Выбор сортировки

Таким образом, мы заменяем 14 на 10. После одной итерации 10, которая оказывается минимальным значением в списке, появляется в первой позиции отсортированного списка.

Выбор сортировки

Для второй позиции, где находится 33, мы начинаем сканировать остальную часть списка линейным способом.

Выбор сортировки

Мы находим, что 14 является вторым самым низким значением в списке, и оно должно появиться на втором месте. Мы поменяем эти значения.

Выбор сортировки

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

Выбор сортировки

Тот же процесс применяется к остальным элементам в массиве.

Ниже приведено графическое изображение всего процесса сортировки –

Выбор сортировки

Теперь давайте изучим некоторые программные аспекты сортировки.

Алгоритм

Step 1 − Set MIN to location 0
Step 2 − Search the minimum element in the list
Step 3 − Swap with value at location MIN
Step 4 − Increment MIN to point to next element
Step 5 − Repeat until list is sorted

ПСЕВДОКОД

procedure selection sort 
   list  : array of items
   n     : size of list

   for i = 1 to n - 1
   /* set current element as minimum*/
      min = i    
  
      /* check the element to be minimum */

      for j = i+1 to n 
         if list[j] < list[min] then
            min = j;
         end if
      end for

      /* swap the minimum element with the current element*/
      if indexMin != i  then
         swap list[min] and list[i]
      end if
   end for
	
end procedure

Чтобы узнать о реализации сортировки выбора на языке программирования C, пожалуйста, нажмите здесь .