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

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

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

begin
h:=n div 2; { начальное значение интеpвала }
while h>0 do begin { цикл с yменьшением интеpвала до 1 }
{ пyзыpьковая соpтиpовка с интеpвалом h }
k:=true;
while k do begin { цикл, пока есть пеpестановки }
k:=false; i:=1;
for i:=1 to n-h do begin
{ сpавнение эл-тов на интеpвале h }
if a[i]>a[i+h] then begin
t:=a[i]; a[i]:=a[i+h]; a[i+h]:=t; { пеpестановка }
k:=true; { пpизнак пеpестановки }
end; { if ... }
end; { for ... }
end; { while k }
h:=h div 2; { yменьшение интеpвала }
end; { while h>0 }
end;
Рис. 12. Пример сортировки методом ShellSort
3.2. Быстрая сортировка (QuickSort)
Алгоритм еще называют метод Хoopа. Алгоритм разбивает сортируемый массив опорным элементом на разделы, затем рекурсивно сортирует каждый раздел. Суть метода заключается в том, чтобы найти такой элемент множества, подлежащего сортировке, который разобьет его на два подмножества: те элементы, что меньше делящего элемента, и те, что не меньше его, далее две образованные последовательности опять разбиваются на две и опять сортируются, процесс разбивки повторяется пока не получится массив из двух элементов (рис. 13.).
Реализация алгоритма на языке программирования:
Program QuickSort;
Var A : array[1..20] of integer;
N,T : integer;
Procedure Sort(p,q : integer);
{p,q - индексы начала и конца сортируемой части массива}
Var i,j,r : integer;
Begin if p<q then {массив из одного элемента тривиально упорядочен} begin r:=A[p];
i:=p-1;
j:=q+1;
while i<j do begin repeat i:=i+1;
until A[i]>=r;
repeat j:=j-1;
until A[j]<=r;
if i<j then begin T:=A[i];
A[i]:=A[j];
A[j]:=T;
end;
end;
Sort(p,j);
Sort(j+1,q);
end;
End;
Begin {Определение размера массива A - N) и его заполнение} … {запуск сортирующей процедуры} Sort(1,N);
{Вывод отсортированного массива A} … End.
В приводимом ниже алгоритме быстрой сортировки в качестве значения разбиения используется среднее значение. Хотя такой подход не всегда является наилучшим, он достаточно прост и сортировка будет выполняться правильно [20].
Рис. 13. Пример сортировки методом QuickSort
Можно считать, что число операций сравнения равно nlogn, а число операций обмена равно приблизительно n/6logn. Эти характеристики значительно лучше характеристик рассмотренных ранее сортировок. Однако, следует иметь в виду одно неприятное свойство быстрой сортировки. Если выбираемое для разбиения значение оказывается совпадающим с максимальным значением, то быстрая сортировка превращается в самую медленную с временем выполнения n.[8,9,13]
3.3. Сортировка с помощью двоичного дерева (Tree sort)
Алгоритм сортировки был предложен Дж. У. Дж. Уильямсом и Р.У. Флойдом в 1964 году. Алгоритм является модификацией сортировки выбором. В отличии от сортировки выбором минимальный (или максимальный) элемент исходной последовательности выбирается за меньшее количество операций.[15,16,18]
Основная идея алгоритма состоит в построении бинарного дерева (рис. 14 А) и последующее его сортировке (рис. 14 В-Н). Бинарное дерево имеет следующую структуру, при которой i элемент последовательности (предок) имеет два элемента (потомка) с номерами 2i и 2i+1. Дерево имеет нормальную форму, если любой элемент предок больше своих потомков.[20]
Алгоритм преобразования массива в бинарное дерево:
Для последовательности x[1],x[2],...,x[n] устанавливается k=n/2. Далее перебираются элементы массива в цикле справа налево для i=k,k-1,...,1. Если неравенства xi > x2i, xi > x2i+1 не выполняются, то повторяются перестановки xi с наибольшим из потомков. Перестановки завершаются при выполнении неравенств xi > x2i, xi > x2i+1.
Алгоритм сортировки пирамиды:
Элементы с индексами x[1] и x[n] переставляются местами. Уменьшить количество сортируемых элементов на 1 (n=n-1) теперь элемент x[n] не рассматривается. Далее рассматривается массив x[1],x[2],...,x[n-1. Полученный массив преобразовывается в дерево. Элемент x[1] переставляется с наибольшим из потомков. Признаком окончания таких перестановок будет то что x[1] займет место элемента x[i] и при этом будут выполняться неравенства x[i] > x[2i], x[i] > x[2i+1].Алгоритм заканчивает свою работу когда n=1.
Общее число операций сравнения и перестановок в данном алгоритме пропорционально (nlog(n)), значит, вычислительная сложность алгоритма составит (nlog(n)), что позволяет говорить о том, что сортировка бинарными деревьями является быстрой сортировкой.
Рис. 14. Пример сортировки массива методом Tree sort
Примеры реализации в программном коде[7,10,11,14]:
min := 1;
max := N; {array size: var A : array [1..N] of integer}
repeat
mid := min + (max - min) div 2;
if x > A[mid] then
min := mid + 1
else
max := mid - 1;
until (A[mid] = x) or (min > max)
4. Анализ алгоритмов сортировки
Единственного эффективного алгоритма сортировки нет, ввиду множества параметров оценки эффективности:
Время – один из основных параметров, определяющий быстродействие алгоритма. Еще этот параметр называют вычислительной сложностью. Для упорядочивания важно лучшее, среднее и худшее поведение алгоритма в зависимости исходного от размера сортируемой последовательности (обозначается - n). Принято считать хорошим поведением алгоритма – величину O(n log n) (большая буква “О” обозначает сложность алгоритма) и плохим поведение алгоритма – величину O(n2). Идеальное поведение для упорядочивания величина равная O(n). Время сортировки зависит от числа операций сравнения и операций обмена.
Усложненные методы требуют большого числа операций, и поэтому для достаточно малых n прямые методы оказываются быстрее, хотя при больших n их использовать, конечно, не следует. Быстрая сортировка является наиболее эффективным алгоритмом из всех известных методов сортировки, но все усовершенствованные методы имеют один общий недостаток – невысокую скорость работы при малых значениях n. Худшая по производительности из простых сортировок (простая сортировка обменом) работает в несколько раз медленнее быстрой сортировки - Хоора. Самая быстрая из простых сортировок (простая сортировка вставками) работает медленнее в несколько раза, чем самая худшая по производительности из сложных сортировок - сортировка Шелла [4]. При увеличении размеров массива, указанные эффекты проявляются еще в большей степени.
Приведем сравнительную сводную таблицу со значением сложности для основных алгоритмов сортировки (см. таблица 1 и таблица 2).
Алгоритмы устойчивой сортировки Таблица 1
Название
Сложность худшая
Сортировка пузырьком (Bubble sort)
O(n2)
Сортировка вставками (Insertion sort)
O(n2)
Алгоритмы неустойчивой сортировки Таблица 2
Название
Сложность худшая
Сортировка выбором (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 экспериментов, в таблице представлены усредненные результаты, полученные в ходе их проведения [17]:
Скорости работы алгоритмов Таблица 3
Количество элементов
Метод сортировки
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. Таким образом можно сделать вывод, что при разработке программ требующих упорядочивания массивов большого объема следует применять сортировку методом бинарных деревьев, как имеющую существенно лучшие показатели по скорости работы.
Устойчивость – сортировка называется устойчивой, если относительный порядок элементов с одинаковыми ключами не меняется при сортировке.[12, c. 226]. Алгоритм сортировка вставками обладает этим свойством, если среди сортируемых ключей (ключ – служит для идентификации элементов при сортировке) имеются одинаковые, после сортировки они остаются в исходном порядке. Быстрый поиск не является устойчивым. Метод, предложенный Дональдом Л. Шеллом, является неустойчивой сортировкой. Метод бинарных деревьев не является устойчивым: по ходу работы массив настолько переупорядочивается, что исходный порядок элементов может измениться случайным образом.
Память - основное требование к методам сортировки – экономное использование памяти. Целесообразно проводить сортировку на месте без копирования. Сортировка вставками и Шелла удовлетворяют этому условию. Сортировка бинарными деревьями не использует дополнительной памяти. Быстрой сортировке требуется стек для организации рекурсии, т.е. он не является и методом сортировки на месте.
Естественность поведения - эффективность метода при обработке уже упорядоченных, или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше. Алгоритм сортировки считается естественных в том случае, когда время сортировки будет меньшим при условии что список упорядочен, и время сортировки будет увеличиваться при менее упорядоченном списке элементов и время сортировки становится наихудшим, когда список элементов упорядочен в обратном порядке. В алгоритме бинарных деревьев поведение неестественно: частичная упорядоченность массива никак не учитывается.
Простота - количество операторов, выполняемых каждым алгоритмом. Более простые алгоритмы вызывают меньше ошибок при программировании.
5. Поиск данных. Методы поиска
Поиск - это процесс определения в исходном множестве элементов, обладающего свойствами или качествами задаваемого.
Процесс поиска информации в случае, когда последовательность не отсортирована, требует последовательного просмотра последовательности. С первого элемента завершая найденным или завершая концом последовательности. Если исходная последовательность отсортирована, целесообразнее использовать двоичный поиск, время выполнения которого значительно меньше.
Время поиска в случае отсортированной последовательности данных пропорционально логарифму числа элементов в последовательности, а поиск в случае не отсортированной последовательности данных, пропорционально числу элементов в последовательности, что намного больше.
Поиск в зависимости от вида обрабатываемых данных делиться на внутренний - поиск в оперативной памяти (поиск в последовательности) и внешний – поиск на внешней памяти.[12, c. 288]
В курсовой работе будут рассмотрены распространенные методы внутреннего поиска.
Основными способами поиска в таблице являются.
Последовательный поиск. Эффективность поиска (среднее число обращений к таблице для нахождения искомой строки) равна n/2.
Логарифмический поиск (бинарный, с помощью двоичного дерева). Число обращений к таблице равно log(n).
5.1. Последовательный поиск
Последовательный или как его еще называют линейный поиск, является самым простым видом поиска, не требует сортировки значений множества, дополнительной памяти и это его основные достоинства. Сложность алгоритма последовательного поиска в среднем равна проверке n/2 элементов. Может так получиться, что проверить надо будет только один элемент, но в худшем варианте необходимо будет проверить все n элементов. В случае не отсортированных исходных данных, последовательный поиск является единственным возможным методом поиска. Недостатком данного вида является то, что его целесообразно использовать, если последовательность не слишком велика.