Методы сортировки и поиска. Сортировка и поиск.

ВВЕДЕНИЕ 3
2 АЛГОРИТМЫ ПОИСКА 8
2.1 Линейный поиск 8
2.2 Поиск с барьером 10
2.3 Двоичный поиск 11
2.4 Поиск подстроки в строке 13
3 МЕТОДЫ ВНУТРЕННЕЙ СОРТИРОВКИ 17
3.1 Сортировка обменом 18
3.2 Сортировка выбором 20
3.3 Сортировка включением 21
3.4 Сравнение методов внутренней сортировки 22
4 МЕТОДЫ ВНЕШНЕЙ СОРТИРОВКИ 24
4.1 Прямое слияние 24
4.2 Естественное слияние 25
4.3 Сбалансированное многопутевое слияние 27
ЗАКЛЮЧЕНИЕ 29
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 32

2 Алгоритмы ПОИСКА

Если необходимо найти необходимую информацию в не отсортированном массиве, то следует прибегнуть к последовательному просмотру массива. Просмотр начинается с самого первого элемента и завершается либо при достижении конца массива, либо, если необходимый элемент найден. Данный метод используется для не отсортированных данных, но он также может использоваться для отсортированных данных, хотя в последнем случае поиск может быть организован значительно быстрее.
Поиск одно из часто необходимых в программировании действий. Существует немало вариаций задачи поиска, но в данной курсовой работе сейчас рассмотрим только поиск в фиксированной последовательности элементов. На вход алгоритма поиска подается последовательность из элементов и некоторый элемент – ключ поиска. Задача заключается в том, чтобы получить на выходе индекс элемента последовательности равному заданному ключу или выяснить, что данного элемента в последовательности не существует [9].


2.1 Линейный поиск
Алгоритм последовательного линейного поиска имеет простой вид. Пусть будет задан массив с элементами a[1],..., a[n] и значение x. Задача поиска формулируется следующим образом: присвоить t значение false, если нет k, такого, что a[k]=x. В противном случае t присвоить значение true, а переменной i присвоить значение n. Тогда алгоритм поиска на языке Паскаль можно записать следующим образом (здесь T – это имя некоторого, достаточно произвольного типа):
const n = 20; {количество элементов в массиве}
var a: array [1..
...

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

2.3 Двоичный поиск
Алгоритм двоичного поиска, как правило, используется для поиска элемента с заданным свойством в последовательностях элементов, упорядоченных по данному свойству. Так при поиске числа с заданным значением необходимо иметь массив, упорядоченный по убыванию или по возрастанию значений элементов исходной последовательности.
Если компоненты массива расположены так, что a[i]a[j] для любых i Идея двоичного поиска состоит в том, что последовательность элементов каждый раз делится пополам и выбирается та часть данной последовательности, где может находиться требуемый элемент. Такое деление продолжается до тех пор, пока часть массива для поиска больше одного элемента, после чего остается проверить оставшийся элемент на выполнение условия поиска.
Существуют две модификации данного алгоритма для поиска первого или последнего вхождения.
...

2.4 Поиск подстроки в строке
В некоторых ситуациях приходится сталкиваться со специфическим видом поиска – поиском подстроки в строке. Пусть имеется некоторая последовательность символов a и подстрока X. Причем длина строки a – n элементов, длина строки x – m элементов и 0 < m < n . Задача поиска заключается в нахождении первого вхождения этого слова Х в указанной строке. Такое действие является типичным для любых систем обработки текстов
Рассмотрим данный поиск на примере.
Пусть a = «воротник», а x = «рот», тогда n=8, a m=3.
Начальное значение i положим равно 0.
Шаг 1. i=0, k =1, k-новый параметр, причем a[i+k] =x[k]
Для примера a[1] <> x[1], т.е. «в» не равно «р», тогда i=1.
Шаг 2. i =1, k = 1
Для примера a[2] <> x[1], т.е. «о» не равно «р», тогда i=2.
Шаг 3. i =2, k = 1
Для примера a[3] = x[1], т.е. «р» равно «р», тогда k:=k+1.
Шаг 4. i =2, k = 2
Для примера a[4] = x[2], т.е. «о» равно «о», тогда k:=k+1.
Шаг 5.
...

3 методы внутренней сортировки

Пусть имеется некоторая последовательность однотипных записей, одно из полей записей выбрано в роли ключа, данное поле называется ключевым. Тип данных ключевого поля должен включать операции сравнения, то есть "=", ">", "<", ">=" и "<=".
Тогда задача сортировки заключается в преобразовании исходной совокупности записей в такую последовательность записей, которая содержит те же записи, но в порядке убывания или возрастания значений ключевого поля. Метод сортировки будет называться устойчивым, если при его применении не изменяется относительное положение записей с равными значениями ключа.
Экономия памяти – это главное требование, предъявляемое к методам сортировки. То есть, при выборе метода сортировки руководствуются критерием экономичного использования памяти. Классификация алгоритмов проводится в соответствии с эффективностью.
Удобно измерять эффективность, подсчитывая число необходимых сравнений ключей и число пересылок элементов.
...

3) Сортировка включением.

3.1 Сортировка обменом
Самым распространенным алгоритмом сортировки является пузырьковый метод (или метод сортировки обменом).
Данный метод основан на выполнении в цикле операций сравнения и при необходимости обмена смежных элементов. Название алгоритма дано ему из-за аналогии с процессом всплывания пузырьков в сосуде с водой. То есть, каждый пузырек всплывает до своего собственного уровня, определяемого соответствующим весом «пузырька».
Другими словами, идея метода сортировки пузырьком заключается в сравнении смежных элементов и их обмене, если они находятся не в нужном порядке. Повторное выполнение таких действий заставляем наименьший элемент "всплывать" в начало последовательности. Следующий проход приведет к всплыванию второго наименьшего элемента массива, и так до тех пор, пока после итерации список не будет полностью отсортирован. Таким образом, массив данных будет отсортирован по возрастанию.
...

4.1 Прямое слияние
Пусть имеется некоторый последовательный файл А, который включает в себя записи а1, а2,…, аn. Каждая такая запись состоит из одного ключевого элемента. Для сортировки прямым слиянием необходимы два вспомогательных файла В и С, размер каждого из них равен n/2. В таблице 5 показан пример внешней сортировки простым слиянием.
Таблица 5. – Внешняя сортировка простым слиянием
Начальное состояние файла A
8 23 5 95 44 33 2 6
Первый шаг
Распределение
Файл B
Файл C
Слияние: файл A

 
8 5 44 2
23 95 33 6
8 23 5 95 33 44 1 6
Второй шаг
Распределение
Файл B
Файл C
Слияние: файл A

 
8 23 33 44
5 95 2 6
5 8 23 95 2 6 33 44
Третий шаг
Распределение
Файл B
Файл C
Слияние: файл A

 
5 8 23 95
2 6 33 44
2 5 6 8 23 33 44 95

Данный метод сортировки состоит из последовательных шагов. На каждом таком шаге выполняется распределение файла А в файлы В и С, а затем осуществляется слияние файлов В и С в исходный файл А. Файл А содержит записи: 8 23 5 95 44 33 2 6.
...

4.2 Естественное слияние
Недостатком предыдущего метода можно считать то, что при прямом слияние не рассматривается то факт, что исходный файл может быть уже частично отсортирован. Устранить данный недостаток призван метод естественного слияния. Он основан на распознавании упорядоченных подпоследовательностей при распределении и их использование при дальнейшем слиянии. При этом методе сортировка выполняется за несколько шагов, как и при методе прямого слияния. На каждом шаге сначала выполняется распределение исходного файла А по вспомогательным В и С, а потом слияние вспомогательных в исходный файл. При распределении распознается первая серия записей и переписывается в файл B, вторая - в файл C и т.д. В процессе слияние осуществляется сливание первой серии файла В с первой серией файла С, второй серии файла В со второй серией С и т.д.
...

4.3 Сбалансированное многопутевое слияние
В основе сбалансированного многопутевого слияния лежит распределение серий исходного файла по нескольким вспомогательным, то есть по по m вспомогательным файлам B1, B2, ..., Bm и их слияние в m вспомогательных файлов C1, C2, ..., Cm. На следующем шаге производится слияние файлов C1, C2, ..., Cm в файлы B1, B2, ..., Bm и т.д., пока в B1 или C1 не образуется одна серия. Сбалансированное многопутевое слияние является развитием идеи двухпутевого слияния, использованного в предыдущих методах сортировки. Простой пример использования данного метода представлен на рисунке 3.

Рисунок 3 – Многопутевое слияние
Данный метод сортировки имеет следующие преимущества: число проходов алгоритма оценивается как O(log n) (n - число записей в исходном файле), где логарифм берется по основанию n. Порядок числа копирований записей равен O(log n). Но число сравнений не будет меньше, чем при использовании метода простого слияния.
...

ЗАКЛЮЧЕНИЕ

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

1. Алексеев Е.Р., Чеснокова О.В., Кучер Т.В., Самоучитель по программированию на Free Pascal и Lazarus. - Донецк.: ДонНТУ, Технопарк ДонНТУ УНИТЕХ, 2009. – 503 с.
2. Вирт Н. Алгоритмы и структуры данных. М.: Мир, 1989. - 360с.
3. Гагарина Л.Г., Алгоритмы и структуры данных: Учебное пособие. – М.: ИНФРА-М, 2009. – 304 с.: ил, ISBN 978-5-16-003-682-3.
4. Демидов Д.В., Основы программирования на языке Pascal в примерах: Учебное пособие. – М.: НИЯУ МИФИ, 2010. – 172 с.
5. Красиков И.В. Алгоритмы. Просто как дважды два. – М.: Эксмо, 2007. – 256 с. ISBN 978-5-699-21047-3.
6. Павловская Т.А. Паскаль. Программирование на языке высокого уровня: Учебник для вузов. – СПб.: Питер, 2007. – 393с.
7. Потопахин В.В. Искусство алгоритмизации: Учебное пособие. – М.: ДЖК Пресс, 2011. – 320 с., ил., ISBN 978-5-94074-621-8.
8. Алексеев Е.Р., Чеснокова О.В., Кучер Т.В., Самоучитель по программированию на Free Pascal и Lazarus. - Донецк.: ДонНТУ, Технопарк ДонНТУ УНИТЕХ, 2009. – 503 с.
9. Гагарина Л.Г., Алгоритмы и структуры данных: Учебное пособие. – М.: ИНФРА-М, 2009. – 304 с.: ил, ISBN 978-5-16-003-682-3.
10. Демидов Д.В., Основы программирования на языке Pascal в примерах: Учебное пособие. – М.: НИЯУ МИФИ, 2010. – 172 с.
11. Кауфман В.Ш. Языки программирования. Концепции и принципы. – М.: ДЖК Пресс, 2011. – 464 с.
12. Кулаков В.Г., Алгоритмический язык Паскаль: Учебное пособие. – М.: МГИЭМ, 2010. – 41 с.
13. Лозовая С.Ю., Решение типовых задач по программированию: практическое пособие: НИУ БелГУ; НИУ БелГУ.-Белгород: ИПК НИУ "БелГУ", 2011. - 148 с.
14. Мансуров К.Т., Основы программирования в среде Lazarus, 2010. – 772 с.: ил.
15. Марапулец Ю.В., Программирование на языках высокого уровня: Учебное пособие. – КамчатГТУ, 2008. – 189 с. ISBN 978-5-328-00185-4.
16. Меженный О.А., Самоучитель Turbo Pascal, - М:, 2008, 333 с.
17. Павловская Т.А., Паскаль. Программирование на языке высокого уровня: Учебник для вузов. – СПб.: Питер, 2010. – 464с.
18. Попов И.И., Основы алгоритмизации и программирования: Учебное пособие. – 3-е издание – М.: Форум, 2008. – 432 с.
19. Потопахин В.В., Искусство алгоритмизации: Учебное пособие. – М.: ДЖК Пресс, 2011. – 320 с., ил., ISBN 978-5-94074-621-8.
20. Потопахин В.В., Современное программирование с нуля. – М.: ДЖК Пресс, 2010. – 240 с., ил.
21. Сулейманов Р.Р., Методика решения учебных задач средствами программирования: Методическое пособие – М: БИНОМ. Лаборатория знаний 2010, с. 112, ISBN:978-5-9963-0112-6.
22. Решение 50 типовых задач по программированию на языке Pascal – 2012 [Электронный ресурс] – URL: http://el-prog.narod2.ru/ (дата обращения: 10.09.2013).
23. Язык Pascal. Программирование для начинающих. – 2011 [Электронный ресурс] - URL: http://pas1.ru/pascaltextbook (дата обращения: 07.09.2013).