11

Сортировка

Сортировка– это упорядочивание информации путем перестановки элементов в определенном порядке. Если на множестве данных нет отношения порядка, тогда вводится ключ.

Ключ– это элемент, являющийся основанием для сортировки.

Сортировка сложных структур сводится к сортировке ключей.

Метод сортировки считается устойчивым, если элементы с одинаковыми ключами не переставляются.

Имеется последовательность a₁,a₂, …,a_n. На ней определена функцияf(a).

Требуется найти такую перестановку , для которой.

Если – величинаa_i, то упорядочение по возрастанию.

Сортировка дает возможность последовательного поиска элементов, благодаря чему можно существенно сократить время поиска элементов.

Виды сортировки:

1. Внутренняя(на основе одномерного массива)

Элементы хранятся в оперативной памяти, за счет чего осуществляется быстрый доступ к любому элементу без использования дополнительных массивов.

Ограничения связаны с размером оперативной памяти.

2. Внешняя(на основе файлов)

Выполняется над элементами в файле последовательного доступа, расположенными на внешних устройствах. В результате получаем файл с упорядоченными элементами.

При этом необходимо минимизировать объем оперативной памяти, используемой алгоритмом. Допускается использование лишь простых переменных, но не массивов.

Ограничения связаны с временем доступа к файлу.

Основные операции при сортировке:

• сравнение (с)

• перемещение (m)

Так как операция сравнения требует меньшего количества времени, чем операция перестановки. Поэтому улучшение любого алгоритма обычно связано с уменьшением количества перестановок.

Оценка любого алгоритма сортировки производится на основании времени его работы (быстродействия). Лучшие (сложные) алгоритмы сортировки имеют оценку O(nlogn); более простые –O(n²) и применяются при сравнительно небольших значенияхn.

Причины использования простых сортировок:

1. Прозрачность сортировки (определены основные принципы сортировки)

2. Программы короткие и при маленьких nмогут работать быстрее.

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

Пусть определен следующий тип данных

type mas = array [1..n] of typel;

var a: mas;

1. Алгоритмы простой сортировки

1.1. Алгоритм простой вставки (прямого включения)

Метод основан на использовании двух подпоследовательностей:

• готовую отсортированную часть, начиная с первого элемента (a₁..a_i);

• входную, из которой вначале выбираются элементы (a_i..a_n).

На каждом i–ом шаге сортировки из входной последовательности выбираетсяj–ый элемент и в готовой последовательности определяется соответствующее место вставки элементов. На шагеn– 1 массив отсортирован.

Отсортированная часть рассматривается с конца. Элемент a_iсравнивается последовательно сa_i-1,a_i-2… и ищется местоa_iв упорядоченной последовательности. Ищется первый элементa_j<a_iиa_iвставляется правееa_j.

Если выполняется сортировка в порядке возрастания, то осуществляется поиск соответствующего места «справа – налево» до тех пор пока выполняется условие x<a_j, где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;

Оценка ½ перемещений и пересылок

C_min = n – 1 M_min = 3(n–1)

C_ср = (n² + n – 2)/4 M_ср = (n² + 9n –10)/4

C_max = (n² + n – 4)/4 M_max = (n² + 3n –4)/4

Общее число пересылок и перемещений

T_n=О(n²)C=О( n²)M=O(n²)

В качестве улучшения данного алгоритма придется ускорить поиск места для вставки с помощью метода половинного деления (заменить цикл whileв упорядоченной части).Число сравнений уменьшитсяC=О(nlog₂ n), а число перестановок то же, что не дает значительного эффекта.

Если алгоритм применить к отсортированному массиву, то цикл whileвырождается, т.е алгоритм реагирует на предварительную отсортированность массива (хотя бы частичную).