DAA - вставка сортировки

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

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

 Algorithm: Insertion-Sort(A) 
for j = 2 to A.length 
   key = A[j] 
   i = j – 1 
   while i > 0 and A[i] > key 
      A[i + 1] = A[i] 
      i = i -1 
   A[i + 1] = key 

Анализ

Время выполнения этого алгоритма очень сильно зависит от заданного ввода.

Если данные числа отсортированы, этот алгоритм выполняется за O (n) раз. Если заданные числа в обратном порядке, алгоритм запускается за O (n 2 ) времени.

пример

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

2 13 5 18 14

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

Ключ = [2] = 13

a [1] = 2 <13

Своп, без свопа

2 13 5 18 14

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

Ключ = [3] = 5

a [2] = 13> 5

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

2 5 13 18 14

Далее a [1] = 2 <13

Своп, без свопа

2 5 13 18 14

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

Ключ = [4] = 18

а [3] = 13 <18,

а [2] = 5 <18,

а [1] = 2 <18

Своп, без свопа

2 5 13 18 14

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

Ключ = [5] = 14

а [4] = 18> 14

Поменять местами 18 и 14

2 5 13 14 18

Далее а [3] = 13 <14,

а [2] = 5 <14,

a [1] = 2 <14

Так что без обмена

2 5 13 14 18

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

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

2 5 13 14 18