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

Введение

Тема курсовой работы «Алгоритмы поиска и сортировки данных» является очень актуальной на сегодняшний день. Мир информационных технологий постоянно растет и развивается, как и количество информации на всей планете. Информационные технологии решают такую задачу, как правильное, эффективное и удобное сохранение всех имеющейся информации на неких носителях. Для этого были созданы дискеты, диски, флэш-карты, винчестеры, базы данных, которые сохраняют информацию непосредственно в памяти ЭВМ. Кроме этого, теперь, всю необходимую информацию, пользователи, также могут сохранять и в сетях Всемирной паутины (Интернет). Но просто сохранить всю имеющуюся информацию недостаточно, ее необходимо организовать таким образом, чтобы искать необходимые, данные было просто и легко. Именно поэтому, изучение алгоритмов сортировок и поиска очень популярно в настоящее время.

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

Также, для поиска информации, в сети Интернет (а эти сети содержат неимоверно огромное количество информации), используется некое программное обеспечение, которое включают в свой состав поисковые программы, такие как Google, Yandex, Rambler и так далее. Эти программы, для того чтобы быстро и эффективно найти по запросу пользователя некую информацию, используют два алгоритма:

1. Алгоритм сортировки, с помощью которого происходит процесс упорядочивания, перегруппировки всей имеющейся информации;
2. Алгоритм поиска, направленный на нахождение в упорядоченном множестве, искомой информации.

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

В данной курсовой работе в качестве объекта исследования выступают «Структуры и алгоритмы обработки данных», а предметом исследования являются «Алгоритмы поиска и сортировки данных».

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

Обзор источников. Рассмотрим основные используемые источники.

В своем известном произведении «Искусство программирования», известный программист Дональд Эдвин Кнут высказал, такую мысль, что сортировка и поиск играют важную роль в программировании.[11] автор уделяет особое внимание тому, как происходит работа отдельно взятого алгоритма, и, с помощью примеров, объясняет, насколько они важны в настоящее время.

В своем произведении автор Ивановский С.А. «Структуры и алгоритмы обработки данных» уделяет особое внимание важности алгоритмам сортировки и поиска данных, рассматривает детально работу каждого из них. Автор приводит множество примеров и иллюстраций, что помогает более явно понять данную тему. [8]

Глава 1 Структура и алгоритмы обработки данных

Как уже было сказано, мир информационных технологий не стоит на месте и постоянно развивается, и вместе с ним появляется все большее количество информации. Информационные технологии помогают всю эту информацию сохранить и упорядочить (сортировать) так, чтобы это было удобно пользователям. Все данные, которые сохранены в памяти ЭВМ, представлены в ней в виде двоичных разрядов (битов), которые получили название структуры данных.[2]

Для того, чтобы организовать работу пользователя и компьютера необходим специальный язык с помощью которого пользователь сможет давать компьютеру некие задания. Сначала это был машинный язык Assembler, который самостоятельно переводил значения, вводимые пользователем, в понятные для компьютера двоичные символы. Затем начали появляться усовершенствованные языки программирования, такие как С++, Fortran, Delphi, Pascal, Бейсик и многие другие. Такой язык программирования, как Бейсик очень легок в использовании, и применяется в основном для написания простейших программ, при обучении молодых и начинающих программистов. Ему на смену пришел следующий язык программирования Fortran, который также очень легок в использовании, но имеет небольшой недостаток – при работе с этим языком необходимо придерживаться строгих правил написания кода. Следующее поколение языков программирования – это языки С++ и Pascal. С++, как и машинный язык переводит символы пользователя в машинные символы, и имеет много других удобных функций. Язык программирования Pascal требует очень точного и четкого написания кодов, следовательно, с его помощью, пользователь может сделать как можно меньше ошибок. При работе с Pascal использует команды, которые схожи со словами английского языка, следовательно, он очень понятен и удобен в использовании. В данной курсовой работе будет рассмотрен именно этот язык программирования[1].

Этот язык программирования очень легок для обучения молодых программистов и с его помощью можно создавать простые и легкие программы, с помощью которых программисты получат свой первый опыт работы. С помощью специального алфавита (набор символов) пользователь может прописывать текст создаваемых им программ. Язык программирования Pascal имеет свой синтаксис, который определяет, как правильно создавать конструкции текста.[4]

При написании программы с помощью языка программирования Pascal используются специальные зарезервированные слова, которые очень схожи со словами английского языка. Они используются для того, чтобы обозначить операторов, разделов языка и так далее. На рисунке 1 приведена таблица зарезервированных слов языка программирования Pascal:

Рис.1. Таблица зарезервированных слов в языке Паскаль

Также, при написании кода программы с помощью языка программирования Pascal используются знаки пунктуации, которые также несут в себе некоторый смысл. Эти знаки пунктуации рассмотрим на рисунке 2:

Рис.2. Таблица знаков пунктуации в языке Паскаль

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

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

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

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

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

И четвертое правило – это массовость. При своей работе алгоритм оперирует большим количеством объектов.

Алгоритмы предоставляются несколькими способами.

• Формульно-словесный способ. Это способ основан на том, что при создании такого алгоритма, используется четко поставленные действия, совместно со словесными объяснениями;
• Способ алгоритмического языка. Такой способ включает в себя математические формулы или выражения, словесные пояснения, а также служебные слова;
• Графический способ (блок-схемы). В этом случае, работа алгоритма показана с помощью некоторых геометрических фигур, которые показаны на рисунке 3:

Рис.3. Графический способ предоставления алгоритмов

Рассмотрим пример: пользователю необходимо выяснить следующее: С=. Алгоритм необходимо представить в виде блок схемы:

Рис. 4. Блок схема алгоритма

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

Также необходимо уделить внимание и таким моментам в работе алгоритмов – это время выполнения работы, ее сложность и объем дополнительной памяти, который необходим во время выполнения его работы.

Для определения сложности разработаны некоторые критерии, которые показаны на рисунке 5:

Рис. 5. Сложность работы алгоритмов

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

1. Внутренние структуры данных (данные, находящиеся в оперативной памяти ЭВМ);
2. Внешние структуры данных (данные, находящиеся в памяти внешних устройств).

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

В данной главе курсовой работы был изучен язык программирования Pascal. Было уделено особое внимание понятию «алгоритм». Были изучены его свойства, виды предоставления алгоритма, его сложность, время работы. Алгоритмы выполняют очень большой объем работы, и на современном этапе, без него очень тяжело обойтись. В следующих главах будут рассмотрены важные алгоритмы: сортировки и поиска.

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

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

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

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

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

Рис. 6. Алгоритмы сортировок

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

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

• Внутренняя сортировка (сортировка файлов). Такая сортировка применяется для данных, которые находятся во внутренней памяти ЭВМ;
• Внешняя сортировка (сортировка массивов). Такая сортировка применяется для упорядочивания данных, которые сохранены на внешней памяти (магнитные ленты, флэшки, переносных винчестерах и так далее). Хотя, внешняя сортировка значительнее медленней внутренней, но все равно она пользуется популярностью у пользователей, которые заботятся об экономном использовании памяти компьютера.

Во время работы алгоритма сортировки, функция упорядочивая данных, не рассчитывается по некоему установленному правилу, а содержится в виде явной компоненты (по другому - поля). Значение такой компоненты носит название ключа алгоритма сортировки, и он используется для определения элемента.[20]