КУРСОВАЯ РАБОТА
на тему: «Сравнительноеисследование эффективности методов сортировки»
Задание
Сравнительноеисследование эффективности методов сортировки.
Базовая структураданных – вектор
Методы сортировки –метод Шелла, метод Флойда.
Примечание: Сравнениеприводиться в виде графиков зависимостей количества сравнений и числаперестановок элементов от объёма данных.
Введение
В последние годыпрограммирование для вычислительных машин выделилось в некоторую дисциплину,владение которой стало основным и ключевым моментом, определяющим успех многихинженерных проектов, а сама она превратилась в объект научного исследования. Изремесла программирование перешло в разряд академических наук. Первый крупныйвклад в ее становление сделали Э. Дейкстра и Ч. Хоар. Основноевнимание в их работах уделяется построению и анализу программ, а более точно – структуреалгоритмов, представляемых текстом программы. Программы представляют собойконкретные, основанные на некотором реальном представлении и строении данныхвоплощения абстрактных алгоритмов.
Алгоритм – этоформально описанная вычислительная процедура, получающая исходные данные,называемые его аргументом, и выдающая результат вычислений на выход. Алгоритмыстроятся для решения тех или иных вычислительных задач. Формулировка задачиописывает, каким требованиям должно удовлетворять решение задачи, а алгоритм,решающий эту задачу, представляет собой метод, применение которого позволяетполучить объект, удовлетворяющий этим требованиям. В настоящее время слово«алгоритм» ассоциируется, в основном, с компьютерами и другими средствамивычислительной техники, хотя разработка алгоритмов началась на заре развитияматематики, задолго до появления вычислительных машин. Формула Герона длявычисления корня квадратного из неотрицательного числа, процесс нахождения наибольшегообщего делителя, выявление простых чисел из чисел натурального ряда («решетоЭратосфена») всё это алгоритмы, которые можно реализовать посредством любогоязыка программирования и на любой современной ЭВМ. В последние полвекатворческий процесс создания вычислительных алгоритмов стал наиболееинтенсивным, это связано с возникновением, совершенствованием и развитиеминформационных технологий и всей компьютерной индустрии.
Для тогочтобы разрабатывать собственные алгоритмы целесообразно сначала изучить ужесуществующие, методы анализа их параметров и эффективности. Тем более, чтомировой опыт программирования насчитывает их великое множество. Рассматриваяразличные методы решения одной и той же задачи, полезно проанализировать,сколько вычислительных ресурсов они требуют (времени работы, памяти), и выбратьнаиболее эффективный. Конечно, в этом случае нужно учитывать какая модельвычислительной системы используется для их выполнения: однопроцессорная ЭВМ илимногопроцессорный комплекс. При анализе времени работы алгоритма следуетучитывать ряд факторов, оказывающих определенное воздействие на результат:размерность исходных данных, структура данных в которую они организованы, их местахранения и размещения во время выполнения программы.
При сравненииметодов сортировки, с точки зрения их эффективности, выполняют многократноетестирование разработанной программы на данных различной длины со всевозможнымиперестановками. Для каждого входного вектора значений размерности n определяется числосравнений sr и число обменов m, выполняемых с его координатами в процессеработы алгоритма. Полученные статистические данные отражают средние значенияпараметров, на основании которых можно сделать вывод об эффективности того илииного метода сортировки или поиска.
При сравненииспособов организации некоторой логической структуры данных, например, спискаили дерева, в процессе анализа учитывают, насколько быстро и просто выполняетсяеё формирование посредством некоторой физической реализации, сколько времени ивычислительных ресурсов требуется для её модификации (вставки, удаления,перестроения), как быстро осуществляется поиск необходимой информации в такойструктуре.
Алгоритмы сортировки информации
Хотя в словарях слово«сортировка» определяется как процесс разделение объектов по виду или сорту,программисты традиционно используют его в гораздо более узком смысле, обозначаяим такую перестановку предметов, при которой они располагаются в порядкевозрастания или убывания.
Под сортировкой массивовпонимают процесс перестановки элементов массива в определенном порядке.
Цель сортировки –облегчить последующий поиск элементов в отсортированном массиве.
Методы сортировкиважны при обработке данных, с ними связаны многие фундаментальные приемы построенияалгоритмов.
Сортировки могут бытьвыполнены с использованием различных алгоритмов: как простых, так и усложненных(но более эффективных). Основное требование к методам сортировки: экономноеиспользование памяти и быстродействие. Первое требование может быть выполнено,если переупорядочение элементов будет выполняться на том же месте. Хорошиеалгоритмы сортировки требуют порядка n *log/>n/>сравнений.
Простые методысортировки можно разбить на три основных класса в зависимости от лежащего в ихоснове приема:
1. сортировкавыбором;
2. сортировкаобменом;
3. сортировкавключением.
Простые методысортировки требуют порядка n*n сравнений элементов (ключей).
Простые методысортировки.
Сортировкапосредством простого выбора.
Сортировка основанана идее многократного выбора (находится сначала наибольший элемент, затемвторой по величине и т.д.) и сводится к следующему:
1. найти элемент снаибольшим значением;
2. поменятьзначениями найденный элемент и последний;
3. уменьшить наединицу количество просматриваемых элементов;
4. если то.
Алгоритм:
Цикл по количествупросматриваемых элементов {i:=n, n-1,…, 2}
Найти номер k максимальногоэлемента среди a[1], a[2],…, a[i]
Поменять местамизначения элементов a[k] и a[i]
Сортировка обменом(методом пузырька).
Сортировкаобменом предусматривает систематический обмен значениями (местами) тех пар, вкоторых нарушается упорядоченность, до тех пор, пока таких пар не останется.
Алгоритм:
Цикл поколичеству просмотров
Цикл поколичеству сравниваемых значений при очередном просмотре
Если то .
Количествопросмотров (повторений) во внешнем цикле равно n-1. Оно может бытьуменьшено, если i– й шаг показал, что массив уже упорядочен (во внутреннем цикле небыло перестановок).
Сортировкавключением.
Сортировкаоснована на следующем: предполагается, что элементы a[1], a[2], …, a [i-1] упорядочены, a[i] вставляется насоответствующее место, не нарушая свойства упорядоченности. Для этого a[i] сравнивается по очередис a [i-1], a [i-2], …до тех пор, пока небудет обнаружено, что элемент a[i] следует вставить между a[j], a [j-1] (j – номер элемента в a [1…i-1], за которым следует вставить a[i]).Тогда элементы a [j+1],…, a [i-1] сдвигаются на однупозицию вправо, а новая запись помещается в позицию j+1. Удобно совмещатьсравнение и перемещение.
/>
Можно уменьшитьколичество сравнений при организации внутреннего цикла. Для этого используетсяметод барьера: вставляемое значение помещается в начало массива надополнительное 0-е место (a[0]:= a[i]), диапазон индексов расширяется.
/>/>
Метод Шелла
Для алгоритмасортировки, который каждый раз перемещает запись только на одну позицию,среднее время будет в лучшем случае пропорционально N2, потому что в процессесортировки каждая запись должна пройти в среднем />N позиций. Поэтому, еслижелательно получить метод, существенно превосходящий по скорости метод простыхвставок, необходим механизм чтобы записи могли перемещаться большими скачками,а не короткими шажками.
Такой методпредложен в 1959 году Дональдом Л. Шеллом [Donald L. Shell, CACM 2,7 (Java, 1959), 30–32] иизвестен во всем мире под именем своего автора. Пусть имеется массив записейR1, R2, …., R16.
/>
Делим 16записей на 8 групп по две записи в каждой группе: (R1, R9), (R2, R10), …., (R8,R16). Сортируем выбранные пары записей в порядке, например, возрастания, т.е.если в паре (R2, R10): R2 > R10, то R2 и R10 меняем местами: R1, R10, R3,R4, R5, R6, R7, R8, R9, R2, R11, R12, R13, R14, R15, R16. То же самоевыполняется и для других пар записей.
/>
Этосортировка со смещением 8. Этот процесс называется первым проходом. Разделимтеперь записи на четыре группы по четыре записи в каждой: (R1, R5, R9, R13), …,(R4, R8, R12, R16). Затем опять рассортируем каждую группу в отдельности. Этосортировка со смещением 4.
/>
На третьемпроходе отсортируем 2 группы по 8 записей: (R1, R3, R5, R7, R9, R11, R13, R15)и (R2, R4, R6, R8, R10, R12, R14, R16). Это сортировка со смещением 2.
/>
Процессзавершается четвёртым проходом, во время которого сортируются все 16 записей.Это сортировка со смещением 1.
/>
В каждой изпромежуточных стадий сортировки участвуют либо сравнительно короткие массивы,либо уже сравнительно хорошо упорядоченные массивы, поэтому на каждом этапеможно пользоваться методом простых вставок. Метод сортировки Шелла ещёназывается с «убывающим смещением», поскольку каждый проход характеризуетсясмещением h, таким, что сортируются записи, каждая из которых отстоит отпредыдущей на h позиций. Последовательность значений смещений 8, 4, 2, 1 неследует считать неизменной, можно пользоваться любой последовательностью смещений,но последнее смещение должно быть равно 1.
Методсортировки Шелла также известен под именем Shellsort и метода сортировки с«убывающим смещением», поскольку каждый проход характеризуется смещением h, таким, что сортируютсязаписи, каждая из которых отстоит от предыдущей на h позиции.Последовательность значений смещений 8, 4, 2, 1 не следует считать незыблемой;можно пользоваться любой последовательностью ht-1, ht-2, …, h0. но последнее смещение h0должно быть равно 1.Например, в таблице 2 продемонстрированная сортировка тех же данных сосмещениями 7, 5, 3, 1. Как будет показано ниже, выбор значений смещений напоследовательных проходах имеет весьма существенное значение для скорости сортировки./>/>/>/>Сортировка Шелла.
Алгоритм D (сортировка Шелла).Запись R1,…, RNперекомпоновываются в том же адресномпространстве памяти. После завершения сортировки их ключи будут упорядочены: K1/> …/>KN. Для управленияпроцессом сортировки используется вспомогательная последовательность смещений ht-1, ht-2, …, h0, где h0=1; правильно выбрав этизначения в последовательности, можно значительно сократить время сортировки.При t=1этот алгоритм сводится к алгоритму S.
D1: [Цикл по s.] Выполнить шаг D2 при s =t –1, t-2, …, 0, послечего завершить процедуру.
D2: [Цикл по j.] Присвоить h ¬ hs и выполнить шаг от D3 до D6 при h Ki+h для 1/> i /> N-h. Шаги от D3 до D6, по существу, такие же,как соответственно от S2 до S5 в алгоритме S.)
D3. [Установка I, K, R.] Присвоить i ¬ j – h, K ¬ Ki, R ¬ Rj.
D4. [Сравнение K: Ki.] Если K /> Ki, то перейти к шагу D6.
D5. [Перемещение Ri, уменьшение i.] Присвоить Ri+h ¬ Ri, затем i ¬ i – h. Если I>0, то возвратиться кшагу D4.
D6. [Перемещение R на место Ri+h.] Присвоить Ri+h ¬ Ri.
Анализ МетодаШелла.
Длярационального выбора последовательности значений смещений сортировки ht-1,…, h0для алгоритма D нужно проанализироватьвремя выполнения как функцию от этих смещений. Такой анализ приводит кпостановки очень красивых, но еще не до конца решенных математических задач;никому до сих пор не удалось найти наилучшею возможную последовательностьсмещений для больших N. Тем не менее известно довольно много интересных свойствсортировки методом Шелла с убывающим смещением.
Метод Флойда
Данныйвид сортировки не рекомендуется для небольшого числа элементов, как, скажем, внашем программном обеспечении. Однако для большого количества элементовпирамидальная сортировка оказывается очень эффективной, и чем больше числоэлементов, тем эффективнее.
Пирамидальнаясортировка требует N∙Log2N шагов даже в худшем случае. Такие отличные характеристикидля худшего случая – одно из самых выгодных качеств пирамидальной сортировки.
Нов принципе для данного вида сортировки, видимо, больше всего подходят случаи,когда элементы более или менее рассортированы в обратном порядке, т.е. для неехарактерно неестественное поведение. Очевидно, что при обратном порядке фазапостроения пирамиды не требует никаких пересылок.
Пирамидаопределяется как некоторая последовательностьключей
K[L],…, K[R], такая, что
K[i] ≤ K[2i] &K[i] ≤ K [2i + 1], (1)
для всякого i = L,…, R/2.Если имеетсямассив К[1], К[2],…, К[R], который индексируется от 1, то этот массив можнопредставить в виде двоичного дерева. Пример такого представления при R=10 показан на рисунке 2.
/>Рис. 2 –Массив ключей,представленный в виде двоичного дерева
Дерево,изображенное на рисунке 2, представляет собой пирамиду, поскольку для каждого i = 1, 2,…, R/2 выполняется условие(1). Очевидно, последовательность элементов с индексами i = R/2+1, R/2+2,…., R (листьев двоичногодерева), является пирамидой, поскольку для этих индексов в пирамиде нетсыновей.
Способ построения пирамиды «на том же месте» был предложенР. Флойдом. В нем используется процедура просеивания (sift), которую рассмотрим наследующем примере.
Предположим, что дана пирамида с элементами К[3], К[4],…, К[10]нужно добавить новый элемент К[2] для того, чтобы сформировать расширеннуюпирамиду К[2], К[3], К[4],…, К[10]. Возьмем, например, исходную пирамиду К[3],…,К[10], покачанную на рисунке 3, и расширим эту пирамиду «влево», добавивэлемент К[2] =44.
/>Рис. 3 – Пирамида, в которую добавляетсяключ К[2]=44
Добавляемый ключ К[2] просеивается в пирамиду: его значениесравнивается с ключами узлов-сыновей, т.е. со значениями 15 и 28. Если бы оба ключа-сынабыли больше, чем просеиваемый ключ, то последний остался бы на месте, ипросеивание было бы завершено. В нашем случае оба ключа-сына меньше, чем 44,следовательно, вставляемый ключ меняется местами с наименьшим ключом в этойпаре, т.е. с ключом 15. Ключ 44 записываетсяв элемент К[4], а ключ 15 –в элемент К[2]. Просеивание продолжается, поскольку ключи-сыновья новогоэлемента К[4] оказываются меньше его – происходит обмен ключей 44 и 18. Врезультате получаем новую пирамиду, показанную на рисунке 4.
В нашем примере получалось так, что оба ключа-сына просеиваемого элементаоказывались меньше его. Это не обязательно: для инициализации обмена достаточнотого, чтобы оказался меньше хотя бы один сыновей ключ, с которым и производитсяобмен.
Просеивание элемента завершается при выполнении любого из двухусловий: либо у него не оказывается потомков в пирамиде, либо значение егоключа не превышает значений ключей обоих сыновей.
/>Рис. 4 – Просеивание ключа 44 в пирамиду
Алгоритм просеивания в пирамиду допускает рекурсивнуюформулировку:
1)просеиваниеэлемента с индексом temp,
2)привыполнении условий остановки – выход,
3)определениеиндекса qэлемента, с которым выполняется обмен,
4)обменэлементов с индексами temp и q,
5)tmp:= q,
6)перейтик п. 1.
Этот алгоритм в применении к нашему массиву а реализован в этомкоде подпрограммы, который выполняет просеивания в пирамиду с максимальныминдексом R:
begin
k:=2*t;
if k>i then t:=0
else
begin
if k
if Arr[k]>Arr [k-1] then inc(k); Kol_sravFloud:=Kol_sravFloud +1;
if Arr [t-1]>=Arr [k-1] then begin t:=0; Kol_sravFloud:=Kol_sravFloud +1
end else
begin
Kol_sravFloud:= Kol_sravFloud +1;
Tmp:=Arr [k-1];
Arr [k-1]:=Arr [t-1];
Arr [t-1]:=Tmp; // Переустановка Элементов
t:=k;
Kol_PerFloud:= Kol_PerFloud +1;
end;
Код учитывает индексацию вектора а от нуля.
Теперь рассмотрим процесс создания пирамиды из массива а[0], а[1],…,a[Highlndex]. Элементы этого массиваиндексируются от 0, а пирамида от 1. Ясно, что элементы a [N/2], a [N/2+1],…, a[Highlndex] уже образуют пирамиду,поскольку не существует двух индексов i (i= N/2+1, N/2+2, …) и j, таких, что, j=2i (или j=2i+l).Эти элементы составляют последовательность, которую можно рассматривать каклистья соответствующего двоичного дерева. Теперь пирамида расширяется влево: накаждом шаге добавляется новый элемент и при помощи просеивания помещается насоответствующее место. Этот процесс иллюстрируется следующим примером.
Процесс построения пирамиды
44 55 12 42 94 18 06 67
44 55 12 42 94 18 06 67
44 55 06 42 94 18 12 67
44 42 06 55 94 18 12 67
06 42 12 55 94 18 44 67
Примечание – жирным шрифтом отмечены ключи, образующие пирамиду натекущем шаге ее построения
Для того, чтобы получить не только частичную, но и полнуюупорядоченность элементов нужно проделать N сдвигающих шагов, причем послекаждого шага на вершину дерева выталкивается очередной (наименьший элемент).Возникает вопрос, где хранить «всплывающие» верхние элементы? Существует такойвыход: каждый раз брать последнюю компоненту пирамиды (скажем, это будет х),прятать верхний элемент на место х, а х посылать в начало пирамиды в качествеэлемента а[0] и просеивать его в нужное место. В следующей таблице приводятсянеобходимые в этом случае шаги:
Пример преобразования пирамиды в упорядоченную последовательность
06 42 12 55 94 18 44 67
12 42 18 55 94 67 44 06
18 42 44 55 94 67 12 06
42 55 44 67 94 18 12 06
44 55 94 67 42 18 12 06
55 67 94 44 42 18 12 06
67 94 55 44 42 18 12 0б
94 67 55 44 42 18 12 06 – Результат
Из примера сортировки видно, что на самом деле в результате мыполучаем последовательность в обратном порядке. Но это легко можно исправить,изменив направление отношения.
Составпроекта
Данный проект состоитиз трёх форм и трех модулей: модуля главной интерфейсной формы, модуля формыистории сортировки, модуля формы «О программе».
Главная формаимеет вид:
/>
На формерамположены компоненты: RadioGroup1 служащий для выбора вида сортировки и типасортировки; SpinEdit1 – для изменения длины сортируемой последовательности; компонент NDgrid, являющийся окном выводаотсортированного массива; MainMenu1 для вызова окна истории сортировки и окна с информациейо создателях программы; Edit1 служит для вывода массива, также на формеимеется несколько компонентов типа TLabel служащих для пояснения назначения другихкомпонентов.
Форма FormAbout имеет вид:
Данная форма служитдля отображения информации о данной программе.
Данная формасодержит компонент Button1 для закрытия данной формы, компонент Label1 содержащий названиепрограммы и информацию о создателе данной программы. Форма Form2 имеет вид:
/>
Данная формаслужит для графиков
На формерасполагаются компоненты Chart1 и Chart2, которые служат для отображения графиков.