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

На рисунке 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, на котором показан пример работы данного алгоритма сортировки:

Рис. 19. Алгоритм сортировки естественным слиянием

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

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

Рис. 20. Листинг программы алгоритма естественного слияния

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

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

Как видно, что тут выбор остается только за пользователем.

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

Глава 3 Алгоритмы поиска

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

Процесс поиска – это такой процесс, в результате которого, в некотором множестве находится один (или несколько) искомый элемент. Поиск происходит после того, как пользователь задаст программе некие критерии искомого элемента. [13]

Методы поиска принято разделять:

1. Статические;
2. Динамические.

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