Свойство 4 Сортировка вставкой линейна для «почти сортированных» файлов.

Свойство 5 Сортировка выбором линейна для файлов с большими записями и маленькими ключами.

Сортировка Файлов с Большими Записями

Очень часто бывает возможно (и желательно) сделать так, чтобы при сортировке файла состоящего из N элементов любом методом было бы сделано только N операций обмена полной записи посредством косвенной адресации к элементам массива (используя массив индексов или указателей), а саму реорганизацию делать после.

Более конкретно: если массив a[1 N] содержит большие записи, то мы предпочтем использовать массив указателей p[1 N] для того, чтобы знать, где находится очередной элемент массива a, и для произведения псевдообмена. Ниже приведена программа сортировки вставкой с использованием массива указателей:

Для предотвращения излишнего контроля в цикле, в программе опять используются «сторожевые» элементы.

Изначально, индексы идут по порядку. Потом порядок индексов начинает меняться так, чтобы массив a, прочитанный по порядку чтения индексов был упорядочен. Но что, если данные должны быть на самом деле переупорядочены, как это показано на рисунке 6?

Для этого мы можем использовать следующую процедуру, которая физически упорядочивает записи файла используя при этом N перестановок:

procedure rearrange; var i,j,k,t : integer; begin for i:=1 to length(a) do if p[i]<>i then begin t:=a[i]; k:=i; repeat j := k; a[j]:=a[p[j]]; k:=p[j]; p[j]:=j; until k=i; a[j]:=t; end; end;

Сортировка Шелла

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

Основная идея алгоритма состоит в том, чтобы отсортировать все группы файла состоящие из элементов файла отстоящих друг от друга на расстояние h. Такие файлы называются h-сортированными. Когда мы h-сортируем файл по некоторому большому h, мы передвигаем его элементы на большие растояния. Это облегчает работу сортировки для меньших значений h. Процесс заканчивается когда h уменьшается до 1.

var a : array [1 N] of integer; procedure ShellSort1; var i, j, h, v : integer; begin h:=1; repeat h:=h*3+1 until h>100; repeat h:=h div 3; for i := h+1 to N do begin v := a[i]; j:=i; while (a[j-h]>v) and (j>h) do begin a[j] := a[j-h]; j:=j-h; end; a[j] := v; end; until h=1; end;

На рисунке 7 показано, как оболочечная сортировка обрабатывает файл с шагом в ., 13, 4, 1. Серым фоном обозначается сортируемый на данном шаге подфайл.

Приведенная программа использует последовательность . 1093, 364, 121, 40, 13, 4, 1. Могут существовать и другие последовательности – одни лучше, другие хуже.

Свойство 6 Оболочечная сортировка никогда не делает более чем N1.5 сравнений для вышеуказанной последовательности h.

Подсчет Распределения

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

for j:=0 to M-1 do count[j]:=0; for i:=1 to N do inc(count[a[i]] ); for j:=0 to M-1 do count[j]:=count[j-1]+count[j]; for i:=N downto 1 do begin b[count[a[i]]] := a[i]; dec(count[a[i]]); end; a := b;

Упражнения

1. Написать программу сортировки массива 1000 произвольно заданных чисел, используя алгоритм оболочечной сортировки. Найти последовательность h на которой алгоритм работает быстрее всего. Для этого провести серию экспериментов для различных последовательностей и найти ту, которая в среднем работает быстрее. Каждая последовательность должна тестироваться не менее 20 раз.

2. Объяснить сортировку методом подсчета распределения.