Вход

Алгоритмы поиска и сортировки данных.

Рекомендуемая категория для самостоятельной подготовки:
Курсовая работа*
Код 366347
Дата создания 08 апреля 2013
Страниц 42
Мы сможем обработать ваш заказ (!) 29 марта в 12:00 [мск]
Файлы будут доступны для скачивания только после обработки заказа.
1 310руб.
КУПИТЬ

Содержание

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
1.Процесс сортировки данных.
2.Простые методы сортировки
2.1.Сортировка обменом (BubbleSort)
2.2.Сортировка выбором (SelectSort)
2.3.Сортировка вставкой (InsertSort)
2.4.Выводы по проведенному исследованию
3.Усовершенствованные методы сортировки
3.1.Сортировка Шелла (ShellSort)
3.2.Быстрая сортировка (QuickSort)
3.3.Сортировка с помощью двоичного дерева (Tree sort)
4.Анализ алгоритмов сортировки
5.Процесс поиска данных
5.1.Последовательный поиск
5.2.Двоичный поиск
5.3.Интерполяционный поиск
5.4.Анализ алгоритмов поиска
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

Введение

Алгоритмы поиска и сортировки данных.

Фрагмент работы для ознакомления

Рис. 13. Пример кода сортировки массива методом Tree sort
Анализ алгоритма сортировки. Общее число операций сравнения и перестановок в данном алгоритме пропорционально (nlog(n)), значит, вычислительная сложность алгоритма составит (nlog(n)), что позволяет говорить о том, что сортировка бинарными деревьями является быстрой сортировкой.
4. Анализ алгоритмов сортировки
Для каждого метода сортировки имеется несколько алгоритмов реализации. Для того чтобы говорить об эффективности конкретного метода необходимо ответить на ряд вопросов:
Какая средняя скорость сортировки данного алгоритма?
Поведение алгоритма естественное или не естественное?
Как используется память?
Алгоритм сложный в освоении и в реализации?
Единственного эффективного алгоритма сортировки нет, ввиду множества параметров оценки эффективности:
Время – один из основных параметров, определяющий быстродействие алгоритма. Еще этот параметр называют вычислительной сложностью. Для упорядочивания важно лучшее, среднее и худшее поведение алгоритма в зависимости исходного от размера сортируемой последовательности (обозначается - n). Принято считать хорошим поведением алгоритма – величину O(n log n) (большая буква “О” обозначает сложность алгоритма) и плохим поведение алгоритма – величину O(n2). Идеальное поведение для упорядочивания величина равная O(n). Время сортировки зависит от числа операций сравнения и операций обмена.
Усложненные методы требуют большого числа операций, и поэтому для достаточно малых n прямые методы оказываются быстрее, хотя при больших n их использовать, конечно, не следует. Быстрая сортировка является наиболее эффективным алгоритмом из всех известных методов сортировки, но все усовершенствованные методы имеют один общий недостаток – невысокую скорость работы при малых значениях n. Худшая по производительности из простых сортировок (простая сортировка обменом) работает в несколько раз медленнее быстрой сортировки – Хора (смотри таблицу 1). Самая быстрая из простых сортировок (простая сортировка вставками) работает медленнее в несколько раза, чем самая худшая по производительности из сложных сортировок - сортировка Шелла [6]. При увеличении размеров массива, указанные эффекты проявляются еще в большей степени.
Сравнение прямых методов сортировки Таблица 1
Min
Avg
Max
Прямое
включение
C =
M =
n-1
2(n-1)
(n2+n-2)/4
(n2-9n-10)/4
(n2-n)/2-1
(n2-3n-4)/2
Прямой
Выбор
C =
M =
(n2-n)/2
3(n-1)
(n2-n)/2
n*(ln n + 0.57)
(n2-n)/2
n2/4 +3(n-1)
Прямой
обмен
C =
M =
(n2-n)/2
(n2-n)/2
(n2-n)*0.75
(n2-n)/2
(n2-n)*1.5
Приведем сравнительную сводную таблицу со значением сложности для основных алгоритмов сортировки (см. таблица 2 и таблица 3).
Алгоритмы устойчивой сортировки Таблица 2
Название
Сложность худшая
Сортировка пузырьком (Bubble sort)
O(n2)
Сортировка вставками (Insertion sort)
O(n2)
Алгоритмы неустойчивой сортировки Таблица 3
Название
Сложность худшая
Сортировка выбором (Selection sort)
O(n2)
Сортировка Шелла (Shell sort)
O(n log n)
Двоичное дерево сортировки (Tree sort)
O(n log n)
Быстрая сортировка (Quicksort)
O(n log n)
Статистики скорости работы алгоритмов на массивах различной длины.
Чтобы оценить время работы алгоритмов использовалась программа, которая формировала массив псевдослучайных равномерно распределенных на отрезке [0,100000] целых чисел, а затем сортировала этот массив каждым из алгоритмов сортировки. Были получены результаты для массивов с количеством элементов: 5000, 10000, 25000, 50000, 100000. Для каждой размерности были проведены по 5 экспериментов, в таблице представлены усредненные результаты, полученные в ходе их проведения [21]:
Скорости работы алгоритмов Таблица 4
Количество элементов
Метод сортировки
Bubble sort
Insertion sort
Shell sort
Binary tree sort
5000
570
242
54
1
10 000
2 352
990
208
1
25 000
17 160
9 062
1 194
1
50 000
77 234
44 940
5 978
98
100 000
321 169
190 062
24 648
208
Проанализировав полученные результаты, можно сделать несколько выводов. Во-первых несложно заметить, что наилучшую скорость работы показал алгоритм сортировки бинарными деревьями при этом в случае когда количество элементов массива не превышала 50 000 упорядочивание происходило практически мгновенно, остальные алгоритмы показали не высокую скорость работы и применение их при разработке серьезных программ не допустимо. Во-вторых время работы первых четырех алгоритмов ("пузырька", Шелла, простых и бинарных вставок) растет квадратично относительно роста размера упорядочиваемого массива, что подтверждается и теоретическими соображениями, известно, что скорость работы данных алгоритмов оценивается как O(n2). Сортировка методом Шелла показала вполне сносные результаты, но при этом все-таки худшие, нежели сортировка методом бинарных деревьев.
Сортировка алгоритмом бинарных деревьев на частично отсортированных массивах работает долго, выигрыш ее получается только на больших n. Таким образом, можно сделать вывод, что при разработке программ требующих упорядочивания массивов большого объема следует применять сортировку методом бинарных деревьев, как имеющую существенно лучшие показатели по скорости работы.
Устойчивость – сортировка называется устойчивой, если относительный порядок элементов с одинаковыми ключами не меняется при сортировке (рис. 14.).[5, c. 226].
Рис. 14. Пример устойчивой и не устойчивой сортировки
Алгоритм сортировка вставками обладает этим свойством, если среди сортируемых ключей (ключ – служит для идентификации элементов при сортировке) имеются одинаковые, после сортировки они остаются в исходном порядке. Быстрый поиск не является устойчивым. Метод, предложенный Дональдом Л. Шеллом, является неустойчивой сортировкой. Метод бинарных деревьев не является устойчивым: по ходу работы массив настолько переупорядочивается, что исходный порядок элементов может измениться случайным образом.
Память - основное требование к методам сортировки – экономное использование памяти. Целесообразно проводить сортировку на месте без копирования. Сортировка вставками и Шелла удовлетворяют этому условию. Сортировка бинарными деревьями не использует дополнительной памяти. Быстрой сортировке требуется стек для организации рекурсии, т.е. он не является и методом сортировки на месте.
Естественность поведения - эффективность метода при обработке уже упорядоченных, или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше. Алгоритм сортировки считается естественных в том случае, когда время сортировки будет меньшим при условии что список упорядочен, и время сортировки будет увеличиваться при менее упорядоченном списке элементов и время сортировки становится наихудшим, когда список элементов упорядочен в обратном порядке. В алгоритме бинарных деревьев поведение неестественно: частичная упорядоченность массива никак не учитывается.
Простота - количество операторов, выполняемых каждым алгоритмом. Более простые алгоритмы вызывают меньше ошибок при программировании.
Для сортировки больших массивов данных лучший алгоритм это быстрый алгоритм и написание программы сортировки на ассемблере существенно не поможет. Но если надо отсортировать небольшие массивы данных или много небольших массивов, то можно использовать простые методы сортировки. Эту идея реализована в способе оптимизации сортировки слиянием это когда маленькие части массива сортируются методом вставки, а потом происходит слияние отсортированных частей.
5. Процесс поиска данных
Постановка задачи для алгоритмов поиска: имеется последовательность упорядоченных или неупорядоченных данных, необходимо – определить наличие определенного элемента в исходной последовательности.
Поиск - это процесс определения в исходном множестве элементов, обладающего свойствами или качествами задаваемого.
Процесс поиска информации в случае, когда последовательность не отсортирована, требует последовательного просмотра последовательности. С первого элемента завершая найденным или завершая концом последовательности. Если исходная последовательность отсортирована, целесообразнее использовать двоичный поиск, время выполнения которого значительно меньше.
Время поиска зависит от степени упорядоченности исходного массива данных. Время поиска в случае отсортированной последовательности данных пропорционально логарифму числа элементов в последовательности, а поиск в случае не отсортированной последовательности данных, пропорционально числу элементов в последовательности, что намного больше.
Поиск в зависимости от вида обрабатываемых данных делиться на внутренний - поиск в оперативной памяти (поиск в последовательности) и внешний – поиск на внешней памяти.[5, c. 288]
В курсовой работе будут рассмотрены распространенные методы внутреннего поиска.
Основные алгоритмы поиска, которые будут рассмотрены:
Последовательный поиск.
Двоичный поиск.
Интерполяционный.
5.1. Последовательный поиск
Основная идея метода состоит в том, чтобы последовательно в цикле просматривать элементы последовательности до момента обнаружения искомого элемента или до достижения конца последовательности с отрицательным результатом поиска (см. реализацию рис.15.).
Например, если имеет место последовательность 1 2 3 4 5 и надо найти элемент со значением 4, то будет выполнено три шага в цикле и три раза будет выполнена проверка на равенство искомому элементу.
Пример реализации алгоритма в коде [9,14,15,18]:
Рис. 15. Пример реализации последовательного поиска
Анализ алгоритма. Последовательный или как его еще называют линейный поиск, является самым простым видом поиска, не требует сортировки значений множества, дополнительной памяти и это его основные достоинства. Сложность алгоритма последовательного поиска в среднем равна проверке n/2 элементов. Может так получиться, что проверить надо будет только один элемент, но в худшем варианте необходимо будет проверить все n элементов. В случае не отсортированных исходных данных, последовательный поиск является единственным возможным методом поиска. Недостатком данного вида является то, что его целесообразно использовать, если последовательность не слишком велика.
5.2. Двоичный поиск
Основная идея алгоритма заключается в неоднократном делении исходной отсортированной последовательности на две части поиска искомого элемента в одной из этих частей, работа алгоритма завершается, когда элемент делящий последовательность совпадет с искомым или при отрицательном результате поиска. Двоичный поиск, применяется только, если элементы массива отсортированы по возрастанию или убыванию (см. реализацию рис.17.).
Алгоритм метода сортировки можно записать по шагам следующим образом:
Определяется центральный элемент исходной отсортированной последовательности, этот элемент сравнивается с искомым если имеет место совпадение, то поиск завершен, если центральный элемент не равен искомому, если искомое значение меньше центрального поиск продолжается в левой части последовательности (при условии что последовательность отсортирована по возрастанию) в противном случае наоборот поиск продолжается в правой части последовательности. Далее выбранная часть делиться центральным элементом и цикл повторяется до тех пор, пока не будет найден искомый элемент или будут просмотрены все элементы и будут отрицательный результат поиска – искомый элемент не найден.
Если в последовательности имеется несколько элементов со значениями, равными искомому. Алгоритм находит первый равный искомому элементу, который в порядке следования в последовательности может быть ни первым и ни последним.
На рисунке 16 процесс поиска элемента со значением 44 продемонстрирован графически. На первом шаге искомое значение сравнивается со значением элемента в середине массива. Если искомый элемент меньше, то алгоритм продолжает перебирать первую половину списка, если же он больше, чем найденный элемент, поиск продолжается во второй половине списка.
Рис. 16. Пример двоичного поиска числа
Пример реализации алгоритма в коде[9,14,15,18]:
Рис. 17. Пример реализации двоичного поиска
Анализ алгоритма. При двоичном поиске число сравнений в худшем случае равно log n. Для среднего случая это значение будет несколько лучше, а в лучшем случае оно равно единице.
5.3. Интерполяционный поиск
Рассмотренный метод двоичного поиска оптимизирует линейный поиск за счет того что определенная часть элементов массива просто не просматривается, что сокращает время поиска. Существует алгоритм поиска, который оптимизирует двоичный поиск - это интерполяционный метод. В случае равномерного распределения элементов массива следует использовать именно этот метод, он позволит еще больше исключить элементов из просмотра при поиске.
Основная идея метода: в основе лежим интерполяция способность предсказания на основе известных значений неизвестных. Известны, индексы известных значений с их помощью находятся индексы искомых элементов.
Например, рассмотрим пример из предыдущего раздела (см. рис.18.). Дан список из двадцати элементов значения элементов могут быть в диапазоне от 1 до 70. Найдем элемент имеющий значение 44. Находим процент занимаемый числом 44 в диапазоне чисел от 1 до 70. Предполагая, что значения в исходном массиве распределены равномерно, находим предположительную позицию искомого элемента 64% от размера массива – получаем индекс 13. Сравниваем 44 со значением в позиции 13. Если значение меньше, то продолжаем поиск в первой части массива, если больше то во второй части..
 
Рис. 18. Пример интерполяционного поиска
Рассмотрим реализацию алгоритма писка, на примере поиск подстроки в строке (см. рис.19.). Допустим, имеем строку s и подстроку p. Теперь напишем код для поиска подстроки p в строке s.

Список литературы

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

Очень похожие работы
Пожалуйста, внимательно изучайте содержание и фрагменты работы. Деньги за приобретённые готовые работы по причине несоответствия данной работы вашим требованиям или её уникальности не возвращаются.
* Категория работы носит оценочный характер в соответствии с качественными и количественными параметрами предоставляемого материала. Данный материал ни целиком, ни любая из его частей не является готовым научным трудом, выпускной квалификационной работой, научным докладом или иной работой, предусмотренной государственной системой научной аттестации или необходимой для прохождения промежуточной или итоговой аттестации. Данный материал представляет собой субъективный результат обработки, структурирования и форматирования собранной его автором информации и предназначен, прежде всего, для использования в качестве источника для самостоятельной подготовки работы указанной тематики.
bmt: 0.0056
© Рефератбанк, 2002 - 2024