- •Сортировка
- •Методы внутренней сортировки
- •1. Алгоритмы простой сортировки
- •1.1. Алгоритм простой вставки (прямого включения)
- •1.2. Алгоритм простого выбора (выбором)
- •1.3. Алгоритм простого обмена (обменная сортировка)
- •2. Улучшенные алгоритмы сортировки
- •2.1. Алгоритм Шелла
- •2.2. Быстрая сортировка Хоара
- •Внешняя сортировка
Сортировка
Сортировка– это упорядочивание информации путем перестановки элементов в определенном порядке. Если на множестве данных нет отношения порядка, тогда вводится ключ.
Ключ– это элемент, являющийся основанием для сортировки.
Сортировка сложных структур сводится к сортировке ключей.
Метод сортировки считается устойчивым, если элементы с одинаковыми ключами не переставляются.
Имеется последовательность a1,a2, …,an. На ней определена функцияf(a).
Требуется найти такую перестановку , для которой.
Если – величинаai, то упорядочение по возрастанию.
Сортировка дает возможность последовательного поиска элементов, благодаря чему можно существенно сократить время поиска элементов.
Виды сортировки:
Внутренняя(на основе одномерного массива)
Элементы хранятся в оперативной памяти, за счет чего осуществляется быстрый доступ к любому элементу без использования дополнительных массивов.
Ограничения связаны с размером оперативной памяти.
Внешняя(на основе файлов)
Выполняется над элементами в файле последовательного доступа, расположенными на внешних устройствах. В результате получаем файл с упорядоченными элементами.
При этом необходимо минимизировать объем оперативной памяти, используемой алгоритмом. Допускается использование лишь простых переменных, но не массивов.
Ограничения связаны с временем доступа к файлу.
Основные операции при сортировке:
сравнение (с)
перемещение (m)
Так как операция сравнения требует меньшего количества времени, чем операция перестановки. Поэтому улучшение любого алгоритма обычно связано с уменьшением количества перестановок.
Оценка любого алгоритма сортировки производится на основании времени его работы (быстродействия). Лучшие (сложные) алгоритмы сортировки имеют оценку O(nlogn); более простые –O(n2) и применяются при сравнительно небольших значенияхn.
Причины использования простых сортировок:
1. Прозрачность сортировки (определены основные принципы сортировки)
2. Программы короткие и при маленьких nмогут работать быстрее.
Методы внутренней сортировки
Пусть определен следующий тип данных
type mas = array [1..n] of typel;
var a: mas;
1. Алгоритмы простой сортировки
1.1. Алгоритм простой вставки (прямого включения)
Метод основан на использовании двух подпоследовательностей:
готовую отсортированную часть, начиная с первого элемента (a1..ai);
входную, из которой вначале выбираются элементы (ai..an).
На каждом i–ом шаге сортировки из входной последовательности выбираетсяj–ый элемент и в готовой последовательности определяется соответствующее место вставки элементов. На шагеn– 1 массив отсортирован.
Отсортированная часть рассматривается с конца. Элемент aiсравнивается последовательно сai-1,ai-2… и ищется местоaiв упорядоченной последовательности. Ищется первый элементaj<aiиaiвставляется правееaj.
Если выполняется сортировка в порядке возрастания, то осуществляется поиск соответствующего места «справа – налево» до тех пор пока выполняется условие x<aj, гдеx– сортируемый элемент.
Пусть дана последовательность целых чисел:
44 55 12 42 94 18 6 67
1) 44 55 1242 94 18 6 67
2) 12 44 55 4294 18 6 67
3) 12 42 44 55 94 186 67
4) 12 18 42 44 45 94 6 67
…
procedure IncludeSort;
var i,j: integer;
x: typel;
begin
for i:= 2 to n do
begin
x:= a[i]; j:=i – 1;
while (a[i] > x) and (j > 0) do
begin
a[j + 1]:= a[j]; j:= j – 1;
end;
a[j + 1]:= x;
end;
end;
Оценка ½ перемещений и пересылок
Cmin = n – 1 Mmin = 3(n–1)
Cср = (n2 + n – 2)/4 Mср = (n2 + 9n –10)/4
Cmax = (n2 + n – 4)/4 Mmax = (n2 + 3n –4)/4
Общее число пересылок и перемещений
Tn=О(n2)C=О( n2)M=O(n2)
В качестве улучшения данного алгоритма придется ускорить поиск места для вставки с помощью метода половинного деления (заменить цикл whileв упорядоченной части).Число сравнений уменьшитсяC=О(nlog2 n), а число перестановок то же, что не дает значительного эффекта.
Если алгоритм применить к отсортированному массиву, то цикл whileвырождается, т.е алгоритм реагирует на предварительную отсортированность массива (хотя бы частичную).