Файл: Алгоритмы сортировки данных (Структура и алгоритмы обработки данных).pdf

Рис.12. Блок схема алгорима сортировки включением

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

Рис. 13. Листинг сортировки включением

2.4. Сортировка Шелла

Рассматриваемый алгоритм сортировки был изобретен программистом Дональдом Шеллом в 1959 году, и получил свое название в честь своего изобретателя.[7] этот алгоритм выполняет свою работу в несколько проходов. Сначала он сравнивает элементы, которые находятся друг от друга на расстоянии, предположим, 8 позиций, затем, при втором проходе сравниваются элементы, которые располагаются друг от друга на расстоянии, например, 4 позиции. На последнем проходе, данный алгоритм просто упорядочивает оставшиеся неотсортированные элементы между собой. Для лучшего понятия работы данного алгоритма сортировки, рассмотрим следующий пример:

На данной таблице видно, что алгоритм сортировки методом Шелла выполнил свою работу за три прохода по массиву. Зрительно можно сказать, что алгоритм разбивает массив на группы. В данном случае группа «7 и 5» произвела смену мест с группой «4 и 3». Массив уже выглядит упорядоченным, следующий шаг, смена мест между собой элементов «4» и «2», а также элементов «7» и «6». На последнем шаге, алгоритм лишь произвел смену мест двух элементов, которые находились не на своем месте – это элементы «6» и «5».

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

На рисунке 14 показана блок схема алгоритма сортировки методом Шелла:

Рис.14. Сортировка методом Шелла

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

Рис.15. Листинг алгоритма сортировки методом Шелла

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

2.5. Сортировка разделением

Данный алгоритм сортировки имеет несколько названий – сортировка разделением, сортировка методом Хоара (названа так в честь программиста К.Хоара, который ее изобрел в 1962 году), а также быстрая сортировка. Алгоритм сортировки разделением считается, на сегодняшний день, считается наиболее универсальным алгоритмом, и работает очень быстро, поэтому и получил такое название.

Смысл данной сортировки заключается в том, что в массиве выбирается некий элемент с максимальным значением, и этот элемент сравнивается с другими элементами. И, все минимальные элементы отсортировываются в начало массива, а максимальные в конец массива. [18] Это продолжается в несколько проходов по массиву, и каждый раз, в массиве, выбирается один опорный элемент, с которым происходит сравнение других элементов массива, пока весь массив не будет упорядочен. Для того, чтобы лучше понять данное определение, рассмотрим таблицу:

Как видно по таблице, данный массив был отсортирован за 8 проходов. При первом проходе в качестве опорного элемента был принят элемент «9», он поменялся местами со стоящим в конце массива элементом «7» во втором проходе. Далее, при проведении своей работы алгоритм сравнил элемент «9» с элементом «10», и так как 10>9, то они поменялись местами. Затем, элемент «9» произвел смену мест с элементами «8» и «2». Конец массива упорядочен, теперь в качестве главного элемента выступает элемент «7». Работа алгоритма производилась аналогично описанным выше процедурам, и в результате данный массив был отсортирован по возрастанию.

На рисунке 16 показан пример блок схемы алгоритма быстрой сортировки данных:

Рис. 16. Блок схема быстрой сортировки

Для лучшего понятия того, как именно происходит работа данного алгоритма сортировки, необходимо рассмотреть листинг программы:

Рис. 17. Листинг быстрой сортировки

Но эта быстрота рассматриваемой сортировки скрывает за собой и неприятное свойство алгоритма – она требует, при своей работы, выделения дополнительной памяти ЭВМ, что очень неприятно для пользователей.

Итак, в данной главе курсовой работы было уделено внимание алгоритмам внутренней сортировки данных. Были рассмотрены простые способы сортировки, а также их усовершенствованные прототипы. Всех их отличает друг от друга то, что они по разному выполняют свою работу, каждый из них тратит определенный промежуток времени на выполнение своей работы. Простые алгоритмы сортировок очень быстры, но эффективно работают только в массивах с малым количеством элементов. Усовершенствованные алгоритмы сортировки быстро справляются и с большими массивами данных, но требуют выделения дополнительной памяти ЭВМ. Следовательно, какой алгоритм сортировки выбрать пользователю, определяется лично им самым. Алгоритмов сортировки очень много, значит и выбора у пользователя достаточно, он может легко остановить свой выбор на некоем алгоритме, опираясь лишь на собственные нужды в той или иной ситуации.

2.6. Внешняя сортировка

Внешняя сортировка применяется для упорядочивания данных, которые находятся на внешней памяти запоминающих устройств, как:

1. Накопители на магнитных лентах;
2. Накопители на жестких магнитных дисках;
3. Накопители на гибких магнитных дисках;
4. Накопители на оптических дисках;
5. Флэш-память;
6. Твердотелые накопители.

Устройства сохранения данных во внешней памяти позволяют сохранять большие объемы информации, которые при необходимости можно перенести во внутреннюю память ЭВМ. Обычно, внешняя сортировка применяется при работе с базами данных, и от качественной работы внешней сортировки зависит эффективность и производительность систем управления базами данных.

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

В следующих главах будет уделено внимание таким популярным алгоритмам внешней сортировки, как прямое слияние, естественное слияние.

2.7 Прямое слияние

Сортировка слиянием считается наиболее простым алгоритмом внешней сортировки. Этот алгоритм работает очень быстро и эффективно, особенно с такими элементами массива, которые считываются или записываются последовательно. Алгоритм слияния был разработан Д. фон Нейманом в 1945 году.[6] Алгоритм сортировки слиянием работает в три этапа: сначала разбивает массив на две части, потом происходит сортировка каждой из этих частей, и в конце, алгоритм объединяет эти две отсортированные части, и производит конечную сортировку.

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

Алгоритм внешней сортировки прямым слиянием имеет один существенный недостаток – она требует увеличения используемой памяти, так как при ее работе требуется разбивать алгорит на 2 части.

На рисунке 18 показан пример листинга программы сортировки простым слиянием:

Рис.18. Листинг алгоритма прямого слияния

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

2.8. Естественное слияние

Данный алгоритм сортировки – это такой алгоритм, при котором не происходит установление длины серий файла, а сама сортировка определяет количество элементов и упорядоченных подпоследовательностей, выделяемых на каждом шаге сортировки.[19]

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

Для того, чтобы лучше понять данное определение рассмотрим рисунок 19, на котором показан пример работы данного алгоритма сортировки: