Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Способы записи алгоритмов).pdf

Блок-схемы циклических алгоритмов существенно отличаются структурами повторения “повторять ДО” (повторять до выполнения условия окончания цикла) или “повторять ПОКА” (повторять пока выполняются условия продолжения циклического процесса). В первом варианте проверка условий окончания циклических вычислений осуществляется в конце цикла, а во втором – в начале цикла /4, с.6-7/.

1.7 Циклы с неизвестным числом повторений

В циклах с неизвестным числом повторений, процесс решения задачи происходит путем последовательного приближения к исконному результату. Из-за этого процесс является циклическим, поскольку заключается в многократных вычислениях. Начальное приближение Y₀ может выбираться заранее, либо задаваться по определенным правилам. Заканчивается вычисление, если выполнено следующее условие:

Y_i – Y_i-1 ≤ d, где d является допустимой ошибкой вычисления /4, с.8/.

1.8 Сложные циклы

Если вычислительные процессы, содержат два и более включенных друг в друга циклов, то такие процессы называются сложными циклическими процессами или по-другому алгоритмами.

Если цикл содержит внутри себя другой цикл, такие циклы называются внешними, а в противоположность внутреннему (вложенному).

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

В настоящее время алгоритм является неотъемлемой частью в сфере программирования. С помощью правильного построения алгоритмической схемы работают программы, персональные компьютеры и электронно-вычислительные машины.

При помощи алгоритмов решаются задачи не только в сфере программирования, но и на производстве.

2 Обзор алгоритмов сортировки

Сортировка является процессом перестановки объектов данного множества в определённом порядке.

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

Алгоритм сортировки - алгоритм для упорядочения элементов в списке.

Существуют множество методов сортировки, которые имеют, как плюсы, так и минусы.

Алгоритмы сортировки — это достаточно глубоко исследованная область информатики, которая используется в информационно-поисковых системах, в банках и в военкомате.

Важными показателями в быстродействие алгоритмов различных методов сортировки являются:

1. Память. Некоторые алгоритмы требуют дополнительного выделения памяти под временное хранение данных (например, на хранение кода программы).
2. Устойчивость. При устойчивой сортировки взаимное расположение равных элементов не меняется. Это может быть полезным, если они состоят из нескольких полей, а сортировка происходит только по одному из них.
3. Естественность поведения. От естественного поведения зависит эффективность работы метода при обработке уже отсортированных или частично отсортированных данных /5, с.71-72/.

2.1 Алгоритм сортировки вставками

В алгоритме сортировке вставками решается задача сортировки списка имен в алфавитном порядке. Но необходимо отсортировать список путем перестановки его элементов, не перемещая весь список в другое место.

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

Для их сортировки должны повторяться следующие действия:

1. Поднять карточку с именем, первую в неотсортированной части списка;

2. Сдвинуть вниз карточки с именами, которые находятся ниже по алфавиту, чем имя на взятой карточке;

3. Поместить эту карточку на освободившееся место в списке.

Текст программы сортировки на языке псевдокода выглядит так:

procedure Сортировка () assign N the value 2;

while (значение N не превышает )

do (Выбрать N-й элемент списка в качестве опорного; Переместить этот элемент во временное хранилище, оставив в списке пустое место;

while (над пустым местом есть имя, которое по алфавиту размещается ниже, чем опорный элемент)

do (переместить имя, находящееся над пустым местом вниз, оставив в прежней позиции пустое место); Поместить опорный элемент на пустое место в списке assign N the value N+1

где N - счетчик, параметр - количество элементов в списке.

После чего программа сортирует данный список, многократно повторяя следующие действия: «Элемент извлекается из списка, а затем вставляется на надлежащее ему место».

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

Управление внутренним циклом инициализируется, когда опорный элемент извлекается из списка и в нем образуется пустое место.

Операция модификации включает перемещение расположенных выше элементов на пустое место вниз, в результате чего свободное место перемещается вверх по списку. Условие окончания выполняется тогда, когда пустое место будет находится непосредственно под именем, которое по алфавиту размещается выше опорного значения или же достигает верхней позиции списка /6, с.46-47/.

2.2 Пузырьковая сортировка

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

Алгоритм пузырьковой сортировки совершает несколько проходов по списку. При выполнение каждого прохода происходит сравнение соседних элементов друг с другом.

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

Сначала сравниваются первый и второй элементы, потом третий и четвертый и так далее. Элементы, в которых неправильный порядок в паре, переставляются.

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

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

Если при каком-то проходе не произошло ни одной перестановки элементов, то все они стоят в нужном порядке и исполнение алгоритма можно прекратить.

Стоит обратить внимание, что при каждом проходе ближе к своему месту продвигается сразу несколько элементов, хотя гарантировано лишь один элемент занимает окончательное положение.

Рассмотрим алгоритм, который реализует данный вариант пузырьковой сортировки:

BubbleSort(list,N)

list сортируемый список элементов

N – число элементов в списке

numberOfPairs=N

swappedElements=true

while swappedElements do

numberOfPairs=numberOfPairs-l

swappedElements=false

for i=l to numberdfPairs do

if list[i] > list[i+l] then

Swap(list[i], list[i+l] then

swappedElements=true

end if

end for

end while

На данном примере рассмотрим наилучший случай, чтобы предупредить неверную интерпретацию флага swappedElements.

Стоит заметить, что при первом проходе цикл for должен быть выполнен полностью, так как алгоритму потребуется по меньшей мере хотя бы N – 1 сравнение.

Рассмотрим возможности, когда при первом переходе была одна перестановка и когда перестановок не было.

Первый случай: первая перестановка приводит к изменению флага swappedElements на true. Это значит, что цикл while будет выполнен повторно, что потребует еще как минимум N – 2 сравнений.

Второй случай: флаг swappedElements сохранит значение false и выполнение данного алгоритма прекратиться.

Отсюда следует, что в лучшем случае будет выполнено N – 1 сравнений, что происходит при отсутствие перестановок при первом проходе. Наилучший набор данных будет представлять собой список элементов, которые уже идут в требуемом порядке.

И если в наилучшем возможном списке элементы идут в требуемом порядке, то стоит посмотреть, не дает ли обратный порядок элементов наихудший случай.

Если в списке наибольший элемент стоит первым, то он будет переставляться со всеми остальными элементами до самого конца списка.

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

В начале второго прохода на первой позиции уже находится второй по величине элемент, и он переставляется со всеми остальными элементами вплоть до предпоследнего. Этот процесс повторяется для всех остальных элементов, поэтому цикл for будет повторен N—1 раз.

Поэтому обратный порядок входных данных приводит к наихудшему случаю.

Если даже в наихудшем случае цикл for будет повторяться N — 1 раз, то можно уже предполагать, что появление прохода без перестановки элементов равновероятно в любой из этих моментов /6, с.77-79/.

2.3 Сортировка Шелла

Сортировка Шелла была придумана Дональдом Л. Шелл. Данной особенность сортировки состоит в том, что она рассматривает весь список как совокупность перемешанных подсписков.

На первом шаге сортировки подсписки представляют собой просто пары элементов.

На втором шаге в каждой группе по четыре элемента.

Если процесс повторяется, то число элементов в каждом подсписке увеличивается, а число подсписков соответственно будет падать. На рисунке 1 изображены подсписки, которые можно использовать при сортировке списков из 16 элементов.

Рисунок 1 Четыре прохода сортировки Шелла

На рисунке 1 (а) изображены восемь подсписков, которые содержат в себе по два элемента в каждом. Первый подсписок содержит первый и девятый элементы, второй подсписок — второй и десятый элементы, и так далее.

На рисунке 1 (б) изображены четыре подсписка по четыре элемента в каждом. В этом проходе первый подсписок содержит в первый, пятый, девятый и тринадцатый элементы. Второй подсписок будет состоять из второго, шестого, десятого и четырнадцатого элементов.

На рисунке 1 (в) у нас показаны два подсписка, которые состоя из элементов с нечетными и четным номерами соответственно.

На рисунке 1 (г) мы вновь приходим к одному списку.

Сортировка подсписков будет выполняться путем однократного применения сортировки вставками, откуда мы и получаем следующий алгоритм:

Shellsort(list.N)

N число элементов в списке

passes = [log_2 N]

while (passes>=l) do

increment=2"passes-1

for start=l to increment do

InsertionSort(list,N,start,increment)

end for

passes=passes-l

end while

I

В данном алгоритме переменная increment содержит величину шага между номерами элементов подсписка. Мы видим, что на рисунке 1 шаг принимает значения 8, 4, 2 и 1.

В алгоритме мы начинаем с шага, на один меньшего наибольшей степени двойки, меньшей, чем длина элемента списка. Следует, что для списка из 1000 элементов первое значение шага равно 511. При этом значение шага также равно числу подсписков.

Элементы первого подсписка имеют номера 1 и 1+increment; первым элементом последнего подсписка служит элемент с номером increment.

Если при последнем исполнение цикла while значение переменной будет равно единице, то значит и при последнем вызове функции InsertionSort значение increment будет равно единице /6, с.82-84/.

2.4 Корневая сортировка

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

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

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