Сортировка вставкой начинается со значения в индексе 1 и сравнивается со значением в индексе 0. Если значение в индексе 1 меньше значения в индексе 0, значения меняются местами. Индекс увеличивается, и процедура повторяется. Лучший способ убедиться в этом - на примере. Начнем со следующего массива.

Алгоритм начинается с позиции индекса 1.

Выполняется первое сравнение. Алгоритм сортировки вставкой начинается с индекса 1 и сравнивает его с предыдущим индексом, которым в данном случае является индекс 0.

Учитывая, что 7 не меньше 4, значения останутся на своих текущих позициях. Поскольку алгоритм достиг индекса 0, ему необходимо увеличить текущую позицию, чтобы начать следующее сравнение. Теперь он находится в индексе 2. Алгоритм начинает сравнение между значением в индексе 2 и значением в индексе 1.

Поскольку значение в индексе 2 меньше значения в индексе 1, алгоритм будет менять местами значения в этих индексах. Индекс уменьшается на 1, поэтому теперь он снова равен 1. Он сравнивает значение индекса 1 со значением индекса 0.

Поскольку значение в индексе 1 меньше значения в индексе 0, эти два значения поменяются местами. Алгоритм сортировки вставкой подошел к концу цикла сравнения. Он увеличивает начальное значение индекса с 2 до 3.

Алгоритм сравнивает значение индекса 3 со значением индекса 2.

Поскольку значение индекса 3 было меньше значения индекса 2, значения меняются местами. Он уменьшает индекс с 3 до 2 и начинает сравнение с индексом 1.

Поскольку значение индекса 2 меньше значения индекса 1, алгоритм меняет местами два значения. Он уменьшает индекс с 2 до 1 и сравнивает это значение со значением индекса 0.

Поскольку значение индекса 1 не меньше значения индекса 0, значения остаются на своих текущих местах. Значение начального индекса увеличивается до 4.

Алгоритм начинает сравнение значений индекса 4 и индекса 3.

Поскольку значение индекса 4 не меньше значения индекса 3, свопа не происходит. Также стоит упомянуть, что известно, что значения перед индексом 3 меньше значения в индексе 3; нет причин сравнивать значение в индексе 4 с этими значениями, поскольку они уже гарантированно меньше значения в индексе 3. Начальный индекс увеличивается с 4 до 5.

Алгоритм сравнивает значение индекса 5 со значением индекса 4.

Поскольку значение в индексе 5 меньше значения в индексе 4, два значения меняются местами. Индекс уменьшается, и значение индекса 4 сравнивается со значением индекса 3.

Поскольку значение индекса 4 меньше значения индекса 3, два значения меняются местами, и индекс уменьшается с 4 до 3. Значение индекса 3 сравнивается со значением индекса 2.

Поскольку значение в индексе 3 больше, чем значение в индексе 2, значения не меняются местами. Алгоритм подошел к концу и массив отсортирован:

1, 2, 4, 5, 7, 8.

***

Если вам понравилось то, что вы прочитали, моя книга Иллюстративное введение в алгоритмы охватывает этот алгоритм и многое другое.

Моя книга: иллюстративное введение в алгоритмы

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

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

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

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

Уже доступно на Amazon.com