Ничушкина Т.Н., Гуренко В.В. - Разработка алгоритмов простейших программ, страница 5

«Разработка алгоритмов простейших программ»34Рисунок 3.8 – Схема алгоритма сортировки выборомСортировка обменом (метод «пузырька»). Алгоритм прямого обмена основываетсяна попарном сравнении соседних элементов и смене их местами в соответствии с видомсортировки. Например, при сортировке по неубыванию обмен элементов местамипроисходит, если правый элемент в паре меньше левого. Сравнения продолжают до техпор, пока не будут упорядочены все элементы.

Название метода объясняется сходствомпроцесса сортировки с всплыванием пузырьков газа в сосуде с жидкостью: элементымассива можно рассматривать как пузырьки, которые поднимаются к его левой либоправой границе.Пусть, например, массив состоит из элементов (2, 5, 12, 1, 8, 4). Если сортировать повозрастанию, то после первого «прохода» по массиву мы получим его в следующем виде:(2, 5, 1, 8, 4, 12).

После второго «прохода» – (2, 1, 5, 4, 8, 12), после третьего – (1, 2, 4, 5, 8,12).Анализ показывает, что сортировку можно прекратить, когда при очередном проходене понадобилось выполнить ни одной перестановки. Кроме того, следует учесть, чтопосле каждого прохода по меньшей мере один элемент становится на свое окончательноеместо, поэтому можно каждый раз сокращать количество просматриваемых элементов.Схема алгоритма сортировки обменом представлена на рисунке 3.9.ОглавлениеНичушкина Т.Н., Гуренко В.В.

«Разработка алгоритмов простейших программ»35Рисунок 3.9 – Схема алгоритма сортировки обменомСортировка вставками. Алгоритм можно описать следующим образом. На каждомшаге, начиная с i=2, из исходной последовательности извлекается i-й элемент иперемещается в готовую последовательность на нужное место. В реальном процессепоиска подходящего места удобно сначала сравнивать извлеченный элемент с очереднымэлементом aj, а затем либо aj сдвигается вправо, либо ai вставляется на освободившеесяместо.

Процесс поиска завершается при выполнении одного из двух условий: либо найденэлемент aj меньший, чем ai, либо достигнута левая граница массива.Данный случай повторяющегося процесса с двумя условиями окончания являетсятипичным и позволяет воспользоваться хорошо известным приемом «барьера». Для этогонеобходимо расширить диапазон индекса в описании массива от 0 до n. Сортируются nэлементов с индексами от 1 до n, а ячейка с нулевым индексом служит своеобразным«барьером» для срабатывания условий окончания поиска.Схема алгоритма сортировки изложенным методом приводится на рисунке 3.10.ОглавлениеНичушкина Т.Н., Гуренко В.В. «Разработка алгоритмов простейших программ»36Рисунок 3.10 – Схема алгоритма сортировки вставкамиПомимо указанных классических, существует ряд оптимизирующих методовсортировки. Одним из них является метод Шелла. Он состоит в том, чтоупорядочиваемый массив делится на группы таким образом, что в каждой группенаходятся элементы, отстоящие друг от друга на расстоянии d.

Каждая группа сортируетсяметодом вставки, затем массив делится на новые группы с шагом d-1 и т.д. покаколичество групп не станет равным единице. Обычно d выбирается таким образом, чтобыв каждой группе находились два элемента, т.е. d=[n/2].3.1.4. Переформирование массива с изменением его размераПримерами данного класса задач могут служить вычеркивание и вставка элементов,отвечающихопределеннымусловиямилиобладающихзаданнымисвойствами(признаками). При этом для удаления или добавления элемента может производиться какполная, так и частичная обработка массива, когда просматриваются не все элементы, анекоторая их выборка.ОглавлениеНичушкина Т.Н., Гуренко В.В.

«Разработка алгоритмов простейших программ»37Особенностью задач класса является изменение размеров исходного массива. Крометого, вычеркивание или вставка элемента требует сдвига всех тех элементов, которыерасположены после удаляемого или вставляемого.

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

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

Удалить из массива целых чисел все числа, кратные 5.Для алгоритмизации задачи можно предложить два пути:просматривая массив, найти очередной удаляемый элемент, а затем путем сдвигаперенести все элементы, расположенные после него, затирая удаляемый элемент. Вполученном массиве окажется на один элемент меньше.

Изменив размер массива, следуетпродолжить просмотр оставшихся элементов (см. рисунок 3.11, а);просматривая массив, переписывать остающиеся элементы на очередное новое место. Вэтом случае потребуются две переменные для индекса: в качестве первой будемиспользовать параметр цикла, а вторую будем изменять независимо после записиочередного остающегося элемента (см. рисунок 3.11, б).ОглавлениеНичушкина Т.Н., Гуренко В.В.

«Разработка алгоритмов простейших программ»38Рисунок 3.11 – Схемы алгоритма решения задачи:а – с двумя циклами; б – с одним цикломВ первом алгоритме внешний цикл не может быть счетным, поскольку в счетномцикле переменная i меняется на каждой итерации. В нашем алгоритме менять ее неследует в том случае, если i-й элемент удаляется, поскольку в результате сдвига на егоместо переносится следующий, еще не проверенный элемент. Замена счетного цикла нацикл-пока позволяет изменять i только тогда, когда это необходимо.Нетрудно заметить, что вычислительная сложность второго алгоритма меньше, чемпервого.

Но первый алгоритм легче для восприятия. Практика показывает, что второйспособ практически всегда применим, если элементы из массива удаляются. Придобавлении элементов второй способ не применим, поскольку из-за отсутствиядополнительного массива переписываемые элементы рано или поздно начнут затирать ещене проверенную часть массива.Пример 3.8.

Переформировать массив вещественных чисел, добавив в негонулевые элементы после положительных элементов, стоящих на четных местах.ОглавлениеНичушкина Т.Н., Гуренко В.В. «Разработка алгоритмов простейших программ»39В данной задаче, очевидно, необходим второй цикл, причем следует иметь в виду,что при выполнении сдвига ни один из элементов не должен быть затерт, а значит,сдвигать элементы придется с последнего. Кроме того, необходимо обеспечить обходэлементов, расположенных на четных местах. Следовательно, параметр цикла обходанеобходимо менять на две единицы.После обнаружения очередного положительного элемента, стоящего на четномместе, требуется сдвиг всех оставшихся элементов. При этом все элементы, стоявшие начетных местах, окажутся на нечетных. Значит, для правильного добавления нулевогоэлемента необходимо перейти через три элемента, а не через два.

Для того, чтобы врезультате работы алгоритма вывести весь массив, надо также подсчитать количестводобавленных элементов. И, конечно, следует предусмотреть в массиве свободное местодля размещения добавляемых элементов. Схема одного из возможных алгоритмоврешения задачи представлена на рисунке 3.12.Рисунок 3.12 – Схема алгоритма добавления элементов в массивОглавлениеНичушкина Т.Н., Гуренко В.В. «Разработка алгоритмов простейших программ»403.1.5.

Одновременная обработка нескольких массивов или подмассивовК этому классу относятся такие задачи как слияние (объединение) массивов;переписывание элементов, отвечающих определенному условию или имеющих некоторыйпризнак, из одного массива в другой; создание нового массива из элементов исходного,преобразованных по некоторой формуле или подчиняющихся определенному закону.Особенностью задач этого класса является наличие у каждого массива своего индекса,который меняется в своем диапазоне по своему закону. При алгоритмизации подобныхзадач можно использовать как счетные циклы, так и циклы с пред- или постусловием,причем выбор зависит от законов изменения индексов и от того, как грамотно обеспечитьих изменение.Пример 3.9. Даны два массива, отсортированные по возрастанию.

Объединить их втретий массив, сохранив сортировку.Поскольку задача относится к классу задач по одновременной обработке несколькихмассивов, каждому массиву будет усвоен уникальный индекс для доступа к его элементам.Кроме того, размеры исходных массивов в общем случае различны, поэтому у каждогоиндекса будет свой диапазон изменения. Так как в результате работы программы долженбыть сформирован новый массив, элементами которого станут элементы обоих исходныхмассивов, то размер нового массива должен быть равен сумме размеров исходныхмассивов.

Соответственно, диапазон изменения его индекса будет определяться суммойдиапазонов изменения индексов исходных массивов.Примем следующую последовательность действий для решения поставленнойзадачи. Сравниваем первые элементы исходных массивов А и В и наименьший из нихзаписываем первым элементом результирующего массива С. Увеличиваем на единицуиндекс результирующего массива и индекс того из массивов А и В, элемент которого былпереписан. Продолжаем аналогично, последовательно формируя массив С. Так какразмеры исходных массивов различны, то просмотр одного из них закончится раньше.После того, как его элементы окажутся исчерпаны, в массив С дописываем оставшиесяэлементы второго массива.Схема алгоритма решения данной задачи показана на рисунке 3.13.ОглавлениеНичушкина Т.Н., Гуренко В.В.