![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
ГЛАВА 1. Алгоритмы сортировок
1.1 Сортировка методом обмена
Алгоритм сортировки обменами основывается на сравнении и смене мест для пары соседних элементов и продолжении этого процесса до тех пор, пока не будут упорядочены все элементы. Мы повторяем проходы по массиву, сдвигая каждый раз наименьший элемент оставшейся последовательности к левому концу массива. Если мы будем рассматривать массивы как вертикальные, а не горизонтальные построения, то элементы можно интерпретировать как пузырьки в чане с водой, причём вес каждого соответствует его ключу. В этом случае при каждом проходе один пузырек как бы поднимается до уровня, соответствующего его весу(см. табл. 1). Такой метод широко известен под именем «пузырьковая сортировка». В своем простейшем виде он представлен в программе 1. Таблица 1. Пример пузырьковой сортировки
Программа 1. Процедура ExchangeSort
procedure ExchangeSort(var A: mas); var x: integer; begin for i: = N downto 2 do for j: = 2 to i do if A[j] < A[j - 1] then begin x: = A[j]; A[j]: = A[j - 1]; A[j - 1]: = x; end; end;
1.2 Сортировка с помощью выбора
Этот прием основан на следующих принципах: 1. Выбираем элемент с наименьшим ключом. 2. Передвигаем на 1 позицию направо элементы, больше выбранного элемента. 3. Вставляем выбранный элемент в нужную позицию. 4. Затем этот процесс повторяется с оставшимися n-1 элементами, n-2 элементами и т.д. до тех пор, пока не останется один, самый большой элемент. Процесс работы этого метода приведен в таблице 2. Реализация этого алгоритма в программе 2.
Таблица 2. Пример сортировки вставками
Программа 2. Процедура InsertSort
procedure InsertSort(var A: mas); var i, k: Integer; x: integer; begin for i: = 2 to N do begin k: = i; x: = A[i]; while (A[k - 1] > x) do begin A[k]: = A[k - 1]; k: = k - 1; end; A[k]: = x; end; end;
1.3 Сортировка методом Хоара Ч. Хоар изобрел алгоритм сортировки массива и назвал его метод быстрой сортировки(Quicksort). В Quicksort исходят из того соображения, что для достижения наилучшей Эффективности сначала лучше производить перестановки на большие расстояния. Предположим, у нас есть n элементов, расположенных по ключам в обратном порядке. Их можно отсортировать за n/2 обменов, сначала поменять местами самый левый с самым правым, а затем последовательно двигаться с двух сторон. Конечно, это возможно только в том случае, когда мы знаем, что порядок действительно обратный. Но из этого примера можно извлечь нечто действительно поучительное. Давайте, попытаемся воспользоваться таким алгоритмом: выберем наугад какой-либо элемент(назовем его x) и будем просматривать слева наш массив до тех пор, пока не обнаружим элемент Программа 3. Функция Partition function Partition(var A: mas; l, r: Integer; x: integer): Integer; var i, j: Integer; t: integer; begin i: = l - 1; j: = r + 1; repeat repeat j: = j - 1; until x > = A[j]; repeat i: = i + 1; until A[i] > = x; if i < j then begin t: = A[i]; A[i]: = A[j]; A[j]: = t; end; until i > = j; Partition: = j; end; Наша цель – не только провести разделение на части исходного массива элементов, но и отсортировать его. Сортировку от разделения отделяет, однако, лишь небольшой шаг: нужно применить этот процесс к получившимся двум частям, затем к частям, затем к частям частей, и так до тех пор, пока каждая их частей не будет состоять из одного-единственного элемента. Эти действия описываются программой 4. Программа 4. Процедура RecoursiveQuicksort procedure RecoursiveQuick(var A: mas; l, r: Integer); var m: Integer; begin if l < r then begin m: = Partition(A, l, r, A[(l + r) div 2]); RecoursiveQuick(A, l, m); RecoursiveQuick(A, m + 1, r); end; end;
1.4 Сортировка методом Уильямса-Флойда
Метод сортировки массива, предложенный и развитый Вильямсом и Флойдом, носит название алгоритма " пирамиды". Он основан на специальном представлении массива в форме бинарного дерева, обладающего особыми свойствами и называемого " пирамидой". Алгоритм не требует дополнительной памяти. Высокая эффективность алгоритма и гарантированная надежность для самого " худшего" случая часто оказываются решающими факторами, заставляющими отдавать предпочтение этому способу сортировки.
Процесс сортировки состоит из двух этапов. На первом этапе массив преобразуется к виду " пирамиды". На втором этапе осуществляется сортировка " пирамиды".
Под структурой бинарного дерева понимается множество элементов, обладающих иерархией следующего вида:
X[1] X[2] X[3] X[4] X[5] X[6 ] X[7] X[8] X[9]................................
Структура дерева имеет логический характер - в памяти компьютера все элементы массива всеравно расположены последовательно. Каждый элемент в структуре бинарного дерева имеет два элемента-потомка X[2i] и X[2i+1], где i - индекс данного элемента. Элементы массива, являющегося " пирамидой", обладают дополнительными свойствами:
1. Любой элемент пирамиды X[i] не меньше, чем его элементы-потомки X[2i] и X[2i+1] (соответственно первый элемент обладает максимальным значением):
X[i] > = X[2i], X[i] > = X[2i+1]
2. Любая подпоследовательность элементов вида X[n\2+1], X[n\2+2],... X[n] также является пирамидой, обладающей свойствами 1 и 2. После преобразования массива к форме пирамиды сортировка осуществляется следующим образом.
В массиве-пирамиде первый элемент не меньше остальных. Обменяем его с последним элементом и " укоротим" массив на 1 элемент с " хвост а". Наибольший элемент массива окажется последним. " Укороченная" последовательность элементов может уже не быть пирамидой. Поэтому рассмотрим элемент X[1] и его потомки - X[2] и X[3]. Если элемент не меньше потомков, то последовательность является пирамидой. В противном случае меняем местами элемент X[1] и наибольший из потомков: max(X[2], X[3]). Для элемента-потомка, который обменялся значением, повторяется процесс сравнения и обмена с потомками до тех пор, пока последовательность не станет пирамидой. После циклического повторения описанного этапа сортировки пирамида станет отсортированным массивом. Реализация этого алгоритма в программе 5.
Программа 5. Процедура PiramidaSort
Procedure PiramidaSort(var A: mas); Var t, k, i, Y: Integer; Begin For i: = 2 to N do { создание структуры бинарного дерева-" пирамиды" } begin t: = i; while t < > 1 do begin k: = t div 2; If A[k] > = A[t] then t: = 1 else begin Y: =A[k]; A[k]: =A[t]; A[t]: =Y; t: = k; end end end; For i: = N-1 downto 1 do { сортировка массива-" пирамиды" } begin Y: =A[i+1]; A[i+1]: =A[1]; A[1]: =Y; t: = 1; While t < > 0 do begin k: = t+t; If k > i then t: = 0 else begin If k < i then If A[k+1] > A[k] then k: = k+1; If A[t] > = A[k] then t: = 0 else begin Y: =A[k]; A[k]: =A[t]; A[t]: =Y; t: = k end; end; end; end; End;
|