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

Это алгоритм сортировки на основе сравнения на месте. Здесь ведется подсписок, который всегда отсортирован. Например, нижняя часть массива поддерживается для сортировки. Элемент, который должен быть «вставлен» в этот отсортированный подсписок, должен найти свое подходящее место, а затем он должен быть вставлен туда. Отсюда и название,insertion sort.

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

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

В качестве примера возьмем несортированный массив.

Сортировка вставкой сравнивает первые два элемента.

Он обнаружил, что 14 и 33 уже находятся в порядке возрастания. На данный момент 14 находится в отсортированном подсписке.

Сортировка вставкой продвигается вперед и сравнивает 33 с 27.

И обнаруживает, что 33 не в правильном положении.

Он меняет местами 33 на 27. Он также проверяет все элементы отсортированного подсписка. Здесь мы видим, что отсортированный подсписок имеет только один элемент 14, а 27 больше 14. Следовательно, отсортированный подсписок остается отсортированным после обмена.

К настоящему времени в отсортированном подсписке есть 14 и 27. Затем он сравнивает 33 с 10.

Эти значения не отсортированы.

Мы их меняем местами.

Однако свопинг составляет 27 и 10 несортированных.

Следовательно, мы их тоже меняем местами.

Снова мы находим 14 и 10 в несортированном порядке.

Мы снова их меняем местами. К концу третьей итерации у нас есть отсортированный подсписок из 4 пунктов.

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

Алгоритм

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

Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the 
         value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted

Псевдокод

procedure insertionSort( A : array of items )
   int holePosition
   int valueToInsert
	
   for i = 1 to length(A) inclusive do:
	
      /* select value to be inserted */
      valueToInsert = A[i]
      holePosition = i
      
      /*locate hole position for the element to be inserted */
		
      while holePosition > 0 and A[holePosition-1] > valueToInsert do:
         A[holePosition] = A[holePosition-1]
         holePosition = holePosition -1
      end while
		
      /* insert the number at hole position */
      A[holePosition] = valueToInsert
      
   end for
	
end procedure

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