Последовательный или как его еще называют линейный поиск, является самым простым видом поиска, не требует сортировки значений множества, дополнительной памяти и это его основные достоинства. Сложность алгоритма последовательного поиска в среднем равна проверке n/2 элементов. Может так получиться, что проверить надо будет только один элемент, но в худшем варианте необходимо будет проверить все n элементов. В случае не отсортированных исходных данных, последовательный поиск является единственным возможным методом поиска. Недостатком данного вида является то, что его целесообразно использовать, если последовательность не слишком велика.
Двоичный поиск Основная идея алгоритма заключается в неоднократном делении исходной отсортированной последовательности на две части поиска искомого элемента в одной из этих частей, работа алгоритма завершается, когда элемент делящий последовательность совпадет с искомым или при отрицательном результате поиска. Двоичный поиск, применяется только, если элементы массива отсортированы по возрастанию или убыванию (см. реализацию рис.
17.).
Алгоритм метода сортировки можно записать по шагам следующим образом:
Определяется центральный элемент исходной отсортированной последовательности, этот элемент сравнивается с искомым если имеет место совпадение, то поиск завершен, если центральный элемент не равен искомому, если искомое значение меньше центрального поиск продолжается в левой части последовательности (при условии что последовательность отсортирована по возрастанию) в противном случае наоборот поиск продолжается в правой части последовательности. Далее выбранная часть делиться центральным элементом и цикл повторяется до тех пор, пока не будет найден искомый элемент или будут просмотрены все элементы и будут отрицательный результат поиска — искомый элемент не найден.
Если в последовательности имеется несколько элементов со значениями, равными искомому. Алгоритм находит первый равный искомому элементу, который в порядке следования в последовательности может быть ни первым и ни последним.
На рисунке 16 процесс поиска элемента со значением 44 продемонстрирован графически. На первом шаге искомое значение сравнивается со значением элемента в середине массива. Если искомый элемент меньше, то алгоритм продолжает перебирать первую половину списка, если же он больше, чем найденный элемент, поиск продолжается во второй половине списка.
Рис. 16. Пример двоичного поиска числа
Пример реализации алгоритма в коде[9,14,15,18]:
Рис. 17. Пример реализации двоичного поиска
Анализ алгоритма. При двоичном поиске число сравнений в худшем случае равно log n. Для среднего случая это значение будет несколько лучше, а в лучшем случае оно равно единице.
Интерполяционный поиск Рассмотренный метод двоичного поиска оптимизирует линейный поиск за счет того что определенная часть элементов массива просто не просматривается, что сокращает время поиска. Существует алгоритм поиска, который оптимизирует двоичный поиск — это интерполяционный метод. В случае равномерного распределения элементов массива следует использовать именно этот метод, он позволит еще больше исключить элементов из просмотра при поиске.
Основная идея метода: в основе лежим интерполяция способность предсказания на основе известных значений неизвестных. Известны, индексы известных значений с их помощью находятся индексы искомых элементов.
Например, рассмотрим пример из предыдущего раздела (см. рис.
18.). Дан список из двадцати элементов значения элементов могут быть в диапазоне от 1 до 70. Найдем элемент имеющий значение 44. Находим процент занимаемый числом 44 в диапазоне чисел от 1 до 70. Предполагая, что значения в исходном массиве распределены равномерно, находим предположительную позицию искомого элемента 64% от размера массива — получаем индекс 13. Сравниваем 44 со значением в позиции 13. Если значение меньше, то продолжаем поиск в первой части массива, если больше то во второй части.
Рис. 18. Пример интерполяционного поиска Рассмотрим реализацию алгоритма писка, на примере поиск подстроки в строке (см. рис.
19.). Допустим, имеем строку s и подстроку p. Теперь напишем код для поиска подстроки p в строке s.
Рис. 19. Пример реализации интерполяционного поиска Анализ алгоритма. Интерполяционный поиск требует в среднем около loglogn шагов, и поэтому он предпочтительнее бинарного при работе с большими массивами.
Анализ алгоритмов поиска Для не отсортированного массива нужно использовать последовательный поиск, а вот если имеется отсортированный массив, то поиск будет быстрее, если использовать двоичный поиск, в том случае если массив равномерно распределен еще эффективнее будет использовать интерполяционный алгоритм (смотри таблицу 5 и таблицу 6).
Последовательный поиск можно применять для небольших массивов данных, для больших целесообразно использование бинарного поиска или интерполяционный.
Сложность алгоритмов поиска Таблица 5
Название Сложность худшая Линейный поиск O (n) Бинарный поиск O (logn) Интерполяционный поиск O (loglogn)
Сравнение количества операций выполняемых при поиске Таблица 6
Алгоритм Размер массива Количество сравнений линейный поиск: количество элементов:
10 среднее количество сравнений при наличии элемента:
5 количество сравнений при отсутствии элемента:
10 количество элементов:
1000 среднее количество сравнений при наличии элемента:
500 количество сравнений при отсутствии элемента:
1000 бинарный поиск: количество элементов:
10 максимальное количество сравнений при наличии элемента:
8 максимальное количество сравнений при отсутствии элемента:
8 количество элементов:
1000 максимальное количество сравнений при наличии элемента:
10 максимальное количество сравнений при отсутствии элемента:
ЗАКЛЮЧЕНИЕ
Изучение и анализ различных литературных источников по теме работы: алгоритмы сортировки и поиска данных, позволило определить и отразить это в работе основные понятия процессов сортировки и поиска, определить специфику этих процессов, разобраться в основных алгоритмах. Практически все изученные мной книги по программированию включают раздел посвященный данного рода алгоритмам, что говорит о большой значимости данных алгоритмов.
При выполнении курсовой работы удалось рассмотреть и проанализировать лишь небольшую часть основных алгоритмов поиска и сортировки данных, рассмотрены некоторые простые прямые и сложные или как их еще называют усовершенствованные алгоритмы внутренней сортировки массивов. Выбор именно основных алгоритмов позволил детально изучить их. Определить достоинства и недостатки каждого метода.
Из книг по программированию и интернет ресурсов были взяты примеры программного кода реализации алгоритмов на языке Паскаль. Каждый алгоритм (работа алгоритма) рассмотрена на конкретном примере для конкретного исходного массива и последовательного преобразования по шагам этого массива в отсортированный массив. Как уже отмечалось во введении описанию алгоритмов посвящено несколько глав работы, в которых описывается три простых метода сортировки и три усовершенствованных метода.
Детальное изучение основной идеи каждого алгоритма формирует знания необходимые для анализа поставленной перед программистом задачи сортировки и выбора на основе этих знаний самого эффективного алгоритма для решения этой задачи.
В литературе анализ любых алгоритмов сортировки проводится на основании нескольких значимых параметров. Основные из них это конечно быстродействие и использование памяти. Для сравнения алгоритмов в работе было выделено пять основных параметров. Составлены наглядные таблицы для анализа.
Отдельная глава Анализ алгоритмов сортировки описывает результаты работы по сравнению алгоритмов. Можно сделать заключение методы сложных сортировок, эффективнее, чем алгоритмы простых сортировок. В простых методах сортировки массивов время процесса сортировки пропорционально n2 в сложных (n log n). Учитывая не очень хорошую скорость, простые алгоритмы сортировки целесообразно использовать при малых значениях n, при больших значениях более эффективно использовать сложные алгоритмы. В литературе описывался эффективный метод (не описывался в работе, но оговорится о нем хочется для того чтобы не сложилось впечатление об не эффективности простых методов сортировки). Метод используется для сортировки не маленьких массивов данных — это методы слияния, который используют простой метод сортировки для небольших частей исходной последовательности.
В ходе теоретического сравнения были сделаны выводы, что алгоритм сортировки вставок эффективнее алгоритма методом простых перестановок, имеет место меньшее количество сравнений ключей и меньшее число перестановок. В данном разделе приведены сравнительные таблицы с показателем скорости работы алгоритмов.
Вторая часть работы описывает процесс поиска и существующие самые знаменитые алгоритмы поиска. В работе рассмотрены основные самые распространенные методы поиска. Рассмотрено три алгоритма поиска последовательный, бинарный и интерполяционный. Как правило, процессу поиска предшествует процесс упорядочивания данных именно поэтому тема сортировки и поиска рассматриваются в совокупности.
Алгоритм последовательного поиска является самым простым методом поиска, хотя не самым эффективным. Данный вид поиска очень наглядный и легкий в изучении. В работе продемонстрирована основная идея алгоритма, продемонстрирован программный код реализации метода и конечно метод продемонстрирован на конкретном числовом примере.
Алгоритм двоичного поиска приведено основная идея алгоритма описание особенности данного вида поиска, приведен программный код реализации алгоритма на языке Паскаль и продемонстрирован пример реализации на конкретных числовых значениях.
Интерполяционный алгоритм поиска рассмотрен как оптимизирующий алгоритм поиска. Описана основная идея метода, приведен пример кода реализации алгоритма и числовой пример.
Отдельный раздел работы показывает сравнение механизмов поиска. Наиболее эффективным методом поиска данных является двоичный поиск в случае упорядоченности последовательности интерполяционный метод, применяются для отсортированных массивов данных, хотя в случае не отсортированной последовательности можно использовать только последовательный метод.
Безусловно, на сегодняшний день существует большое количество алгоритмов сортировки и поиска данных. Но объем обрабатываемой информации постоянно растет, и найти вовремя необходимую информацию очень актуальная задача для информационного общества, в котором мы сейчас живем. Технологии развиваются и конечно, алгоритмы тоже будут совершенствоваться.
В результате выполнения работы изучен большой объем информации, получены знания по алгоритмам поиска и сортировки по способу их реализации с помощью языка программирования, что позволит в дальнейшем применять эти знания на практике. Выполнение работы было полезным и интересным.
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ Андреева Т. А Программирование на языке Pascal. — М.: Бином. Лаборатория знаний, 2006. — 240 с.
Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы / Пер. с англ. — М.: Вильямс, 2001. 384 с.
Вирт Н. Алгоритмы и структуры данных. — 2-е изд. — СПб: «Невский Диалект», 2001. — 352 с.
Голицина О.Л., Попов И. И. Основы алгоритмизации и программирования: Учебное пособие. — 2-е изд. — М.: ФОРУМ: ИНФРА-М, 2006. — 432 с.
Давыдов В. Г. Программирование и основы алгоритмизации: Учеб. Пособие. — М.: Высш. Шк., 2003. — 447 с.
Клиффорд Ш. Алгоритмы: построение и анализ. — 2-е изд.: Пер. с англ. — М.: «Вильямс», 2005. — 1296 с.
Кнут Д. Искусство программирования, том 3. Сортировка и поиск. — М.: «Вильямс», 2007. — 824 с.
Колдаев В. Д. Основы алгоритмизации и программирования: Учебное пособие / Под ред. проф. Л. Г. Гагариной. — М.: ИД «ФОРУМ»: ИНФРА-М, 2006. — 416 с.
Красиков И. В. Алгоритмы. Просто как дважды два. — М.: Эксмо, 2007. 256 с.
Культин Н. Turbo Pascal в задачах и примерах. — СПб.: БХВ-Петербург, 2006. — 256 с.
Левитин, Ананий В. Алгоритмы: введение в разработку и анализ. — М.: «Вильямс», 2006. — 576 с.
Макконнел Дж. Анализ алгоритмов. Вводный курс.: Пер. с англ. — М.: Техносфера, 2002. 304 с.
Малыхина М. П. Программирование на языке высокого уровня Turbo Pascal. — СПб.: БХВ-Петербург, 2006. — 544 с.
Немнюгин С. А Turbo Pascal — СПб: Издательство «Питер», 2000. — 496 с.
Павловская Т. А. Паскаль. Программирование на языке высокого уровня. — СПб.: Питер, 2007. — 393 с.
Рапаков Г. Г. Программирование на языке Pascal. — СПб.: БХВ-Петербург, 2004. — 480 с.
Скиена С. Алгоритмы. Руководство по разработке. — 2-е изд.: Пер. с англ. — СПб.: «БХВ-Петербург», 2011. — 720 с.
Стивене Р. D elphi. Готовые алгоритмы. — 2-е изд., стер.: Пер.
с англ. Мерещука П. А. ;
М.: ДМК Пресс; - СПб.: Питер, 2004. — 384 с.
Томас Ниман Сортировка и поиск: Рецептурный справочник. // Перевод с английского: П. Н. Дубнер — 2004. — 12 апреля [Электронный ресурс]. URL:
http://www.getinfo.ru/article543.html (дата обращения: 24.
04.2012).
Алгоритмы сортировки — 2009. — 15 яваря [Электронный ресурс]. URL:
http://www.comprog.ru/PascalDelphi/article_4191.htm
Быстрицкий В. Д. Сравнение алгоритмов сортировки массивов.// ALGLIB [Электронный ресурс]. URL:
http://alglib.sources.ru/articles/sort.php (дата обращения: 24.
04.2012).
Кантор Илья Алгоритмы сортировки — 2000 URL:
http://algolist.manual.ru/sort/index.php (дата обращения: 24.
04.2012).
Okcode — 2010. — 29 сентября [Электронный ресурс]. URL:
http://okcode.ru/practicum-po-massivam/ (дата обращения: 24.
04.2012).
Сундукова Т.О., Ваныкина Г. В. Структуры и алгоритмы компьютерной обработки данных.// Интернет-Университет Информационных Технологий — 2011. — 2 февраля [Электронный ресурс]. URL:
http://www.intuit.ru/department/algorithms/staldata/42/ (дата обращения: 24.
04.2012).
