Учимся вставлять правильно. Сортировка “Вставками”

Ранее мы рассмотрели сортировку “Пузырьком” и сортировку методом “Выбора”. В это статье коснемся еще одного метода упорядочения данных. Сортировка “Вставками” так же относится к элементарным сортировкам. Она чуть сложнее для понимания нежели две упомянутые выше, однако несмотря на аналогичную сложность алгоритма O(N^2), считается, что сортировка вставками работает эффективнее на небольших случайных массивах, а так же на частично упорядоченных массивах. На базе сортировки  “Вставками” основан более быстрый метод сортировки “Шелла”. О нем мы поговорим в отдельной статье, сейчас же давайте разберемся как работает алгоритм сортировки “Вставками”, что и куда он вставляет.

Описание алгоритма работы сортировки методом “Вставками”

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

3

4

5

6

4^

3

8

2

6

3

4

5

6^

6

3

8

2

6

3

4

5^

5

6

3

8

2

6

3

4

4

5

6

3

8

2

6

Часть до 4 уже отсортирована. Мы берем 4 и сохраняем значение во временной переменной. Далее сравниваем по направлению в левую сторону с соседними элементами, пока не встретим элемент меньший или равный 4. Как только такой элемент найдется, мы “вставим” перед ним число 4. Однако, нам нужно для этого “раздвинуть” массив, чтобы ячейка перед нужным числом была свободна. В алгоритме сортировки “Вставками” используется довольно таки хитрый прием для смещения элементов массива вправо. Давайте теперь по строчкам. Мы сравниваем 4 и 6, 4<6, поэтому мы записываем 6 на место 4 и двигаемся дальше влево, смотрим вторую строчку таблицы. Теперь сравниваем 4 и 5, 4<5 значит записываем 5 на текущую позицию указателя, который указывает на ячейку с цифрой 6. Этот шаг выполнен на третей строке. Далее сравниваем 4 и 4, 4 = 4, значит можно вставлять 4-ку из сохраненной заранее временной переменной на позицию указателя. Этот шаг в четвертой строке. Теперь мы видим, что массив отсортирован до числа 3, которое идет после 6. При этом массив мы сдвигали вправо каждый шаг алгоритма, выполняя в одной итерации цикла сразу два действия: сравнение и сдвиг массива. Как раз для этого и необходимо записывать во временную переменную элемент, который мы будем “вставлять”.  Мы описали работу алгоритма с середины, как я уже сказал, для упрощения понимания. Вообще же алгоритм идет  слева – направо, визуально можно представить это движение так:

Так же заметим инвариант для сортировки методом “Вставками”:  элементы слева от текущего подготовленного элемента для вставки отсортированы.

Код реализации алгоритма сортировки методом “Вставками” на языке Java:

Вывод работы массива по шагам:

Оставить комментарий:

Ваш email не будет опубликован.