Сортировка вставкой

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

Прежде чем приступить к составлению блок-схемы рассмотрим следующий пример. Пусть известно, что в массиве из восьми элементов первые шесть уже упорядочены, а седьмой элемент нужно вставить между вторым и четвертым. Сохраним седьмой элемент во вспомогательной переменной, так как показано на рисунке 3.10, а на его место запишем шестой. Далее пятый переместим на место шестого, четвертый на место пятого, а третий на место четвертого, тем самым, выполнив сдвиг элементов массива на одну позицию вправо. Записав содержимое вспомогательной переменной в третью позицию, достигнем нужного результата.

Рис. 3.10. Процесс вставки элемента в массив

Составим блок-схему алгоритма (рис. 3.11), учитывая, что возможно описанные выше действия придется выполнить неоднократно.

Организуем цикл для просмотра всех элементов массива, начиная со второго (блок 4). Сохраним значение текущего i -го элемента во вспомогательной переменной X, так как оно может быть потеряно при сдвиге элементов (блок 5) и присвоим переменной j значение индекса предыдущего (i-1) -го элемента массива (блок 6). Далее движемся по массиву влево в поисках элемента меньшего, чем текущий и пока он не найден сдвигаем элементы вправо на одну позицию. Для этого организуем цикл (блок 7), который прекратиться, как только будет найден элемент меньше текущего. Если такого элемента в массиве не найдется и переменная j станет равной нулю, то это будет означать, что достигнута левая граница массива, и текущий элемент необходимо установить в первую позицию. Смещение элементов массива вправо на одну позицию выполняется в блоке 8, а изменение счетчика j в блоке 9. Блок 10 выполняет вставку текущего элемента в соответствующую позицию.

Рис. 3.11. Сортировка массива вставкой

Не нашли, что искали? Воспользуйтесь поиском: