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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1. Алгоритм линейного поиска

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

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

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

На рисунке 21 показана блок схема алгоритма линейного поиска

Рис.21. Блок схема алгоритма линейного поиска

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

Рис. 22. Листинг программы

Рассматриваемый алгоритм сортировки имеет сложность O(N), что характеризует его как простейший алгоритм.

3.2. Поиск делением пополам

Поиск делением пополам наиболее усовершенствованный, чем линейный поиск и выполняет свою работу следующим образом: он разбивает массив, в котором произойдет поиска, на две части, и производит поиск искомого элемента в каждой из них. [16]

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

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

Рис. 23. Блок схема алгоритма поиска делением пополам

По данной блок схеме видно, что работа алгоритма происходит только в уже упорядоченном массиве, и в данном массиве используется условие First < Last. Для того, чтобы найти искомое значение, алгоритм делит массив на две части. В том случае, если индекс Pos окажется равным первому элементу, то переменная отобразит ложное значение, и, следовательно, искомого значения не окажется в массиве. Ну, а если индекс Pos окажется равным (или меньше) последнего значения, то поиска делением пополам закончится «успешно».[3]

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

Рис. 24. Листинг программы

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

3.3. Прямой поиск строки

Еще один алгоритм поиска данных – это алгоритм прямого поиска строки. Алгоритм прямого поиска строки работает таким образом: поэтапно сравнивает первый символ искомого слова с первым и последующими символами слов, которые имеются в изучаемом тексте. В случае, если при сравнении первого символа искомого слова со вторым символом слова в тексте, совпадение не было зарегистрировано программой, то в этой ситуации, она производит сдвиг слова в тексте, и начинает сравнивать искомое слово со вторым словом в тексте. И это сравнение происходит до тех пор, пока совпадение не будет равно 100%, то есть слово будет найдено, либо поиск окончиться неудачей, то есть слово не найдено в искомом тексте.[10]

На рисунке 25 можно увидеть, как именно производит свою работу алгоритм прямого поиска строки:

Рис. 25. Поиск прямой строки

На рисунке видно, то происходит поиск слова «abaa» в тексте Т, и для того, чтобы программа зафиксировала совпадение, алгоритму необходимо было три раза произвести сдвиг слова.

Рис. 26. Листинг алгоритма поиска прямой строки

Чем меньше алгоритму необходимо будет производить сдвиг слова, тем быстрее будет работать сам алгоритм.

3.4 Алгоритм Кнута, Мориса, Пратта

Рассматриваемый алгоритм поиска данных был разработан в 1970 году группой ученых Дональдом Кнутом, Морисом Д. и Пратт В. Второе название этого алгоритма КМП-алгоритм. Этот алгоритм работает следующим образом: алгоритм производит сравнение основной части искомого слова со словами в тексте, и при фиксировании совпадения нескольких символов, программа самостоятельно выполнит все необходимые сдвиги в тексте и сама найдет все оставшиеся символы в тексте. Следовательно, слово будет найдено, но если совпадений не будет обнаружено, то, значит, искомого слова в тексте не имеется.

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

На рисунке 27 показан пример работы КМП-алгоритма:

Рис.27. КМП-алгоритм

Также, для лучшего понятия КМП-алгоритма необходимо рассмотреть листинг алгоритма:

Рис. 28. Листинг алгоритма Кнута, Мориса, Пратта

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

3.5 Алгоритм Боуера-Мура

Алгоритм Боуера-Мура был разработан в 1975 году, в качестве улучшенного варианта КМП-алгоритма.

Представим, как работает алгоритм. В рассматриваемом алгоритме поиск происходит с конца слова. Для этого образно разобьем слово на составляющие. Допустим, что z из алфавита величина R_z – это расстояние от самого правого в слове вхождения z до правого конца слова. При прохождении текста алгоритм зафиксировал расхождение между искомым словом и текстом, которое равно z. И в данном случае, для того, чтобы символ искомого слова совпал с символом z в исследуемом тексте, алгоритм производит сдвиг символа до тех пор, пока они не совпадут.

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

Рис. 29. Алгоритм Боуера-Мура

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

На рисунке 30 показан листинг программы алгоритма Боуера-Мура:

Рис. 30. Листинг алгоритма Боуера-Мура

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

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

Заключение

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

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