Файл: Лекции СД.doc

{ Запись в выходной массив }

bList.Items[j]:=aList.Items[i];

end;

end;

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

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

Первый элемент входного множества примыкает к концу выходного множества. На каждом шаге сортировки происходит перераспределение последовательности: выходное множество увеличивается на один элемент, а входное – уменьшается. Это происходит за счет того, что первый элемент входного множества теперь считается последним элементом выходного.

Затем выполняется просмотр выходного множества от конца к началу с перестановкой соседних элементов, которые не соответствуют критерию упорядоченности. Просмотр прекращается, когда прекращаются перестановки. Это приводит к тому, что последний элемент выходного множества «выплывает» на свое место во множестве.

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

{ Пузырьковая сортировка методом вставок }

procedure InsertionBublSort(aList: TList;

aFirst, aLast: Integer; aCompare: TCompareFunc);

var

i, j: Integer;

Temp: Pointer;

begin

{ Перебор входного массива }

for i:=aFirst+1 to aLast do

{ Входное множество - [i..N-1], выходное множество - [0..i-1] }

begin

{ Запоминается значение нового элемента }

Temp:=aList.List[i];

j:=i;

{ Поиск места для элемента в выходном множестве со сдвигом

цикл закончится при достижении начала или,

когда будет встречен элемент, меньший нового }

while (j > aFirst) and (aCompare(Temp, aList.List[j-1]) < 0) do

begin

{ Все элементы, большие нового сдвигаются }

aList.List[j]:=aList.List[j-1];

{ Цикл от конца к началу выходного множества }

Dec(j);

end;

{ Новый элемент ставится на свое место }

aList.List[j]:=Temp;

end;

end;

Интересная особенность приведенной реализации алгоритма состоит в следующем: значение текущего элемента сохраняется в локальной переменной, а затем при поиске нужного места его вставки (внутренний цикл) происходит перемещение каждого элемента, значение которого больше текущего, на одну позицию вправо, тем самым, перемещая «дыру» в наборе влево. В конце концов, обнаруживается нужное место, и сохраненное значение помещается в освободившееся место. Результат трассировки представлены в табл. 4.10.

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

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

Табл. 4.10. Трассировка сортировки вставками.

Быстрые алгоритмы сортировки

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

Сортировка Шелла была предложена Дональдом Л.Шеллом в 1959 г. Метод пытается повысить скорость работы за счет быстрого перемещения элементов, находящихся далеко от нужных позиций. Сортировка предполагает перемещение таких элементов большими «прыжками», а окончательная установка в нужные позиции может быть выполнена одним из классических способов.

Качественный порядок сортировки остается O(n²), но среднее число сравнений, определенное эмпирическим путем – n·log₂n². Ускорение достигается за счет того, что выявленные «не на месте» элементы при шаге сравнения большем единицы быстрее «всплывают».

Следующий пример представляет реализацию сортировку Шелла, основанную на пузырьковом алгоритме. Исходный шаг сравнения h соизмерим с половиной общего размера последовательности. Сначала выполняется пузырьковая сортировка с интервалом h. Затем величина h уменьшается вдвое и вновь выполняется пузырьковая сортировка, далее h уменьшается еще вдвое и т.д. Последняя пузырьковая сортировка выполняется при h=1.

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

procedure ShellSort(aList: TList; aCompare: TCompareFunc);

var

h, i, t, N: Integer;

Temp: Pointer;

{ Признак перестановки }

k: Boolean;

begin

N:=aList.Count;

{ Начальное значение интервала }

h:=Ndiv2;

{ Цикл с уменьшением интервала до 1 }

whileh> 0do

begin

{ Пузырьковая сортировка с интервалом h}

k:=True;

{ Цикл, пока есть перестановки }

while k do

begin

k:=False;

{ Сравнение элементов на интервале h}

for i:=0 to N-h-1 do

begin

if aCompare(aList.List[i], aList.List[i+h]) = 1 then

begin

{ Перестановка }

Temp:=aList.List[i];

aList.List[i]:=aList.List[i+h];

aList.List[i+h]:=Temp;

{ Признак перестановки }

k:=True;

end;

end;

end;

{ Уменьшение интервала }

h:=hdiv2;

end;

end;

Результаты трассировки примера представлены в табл. 4.11.

Табл. 4.11. Трассировка сортировки Шелла.

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

Полученная последовательность называется отсортированной по h. Затем значение h уменьшается и вновь выполняется сортировка. Уменьшение h происходит до тех пор, пока h не будет равно 1, после чего последний проход будет представлять собой стандартную сортировку методом вставок (точнее сортировку по 1).

Суть сортировки Шелла состоит в том, что сортировка по h быстро переносит элементы в область, где они должны находиться в отсортированном наборе, а уменьшение значения h позволяет постепенно уменьшать размер «прыжков» и, в конце концов, поместить элемент в требуемую позицию. Медленному перемещению предшествуют большие «скачки», сводящиеся к простой сортировке методом вставок, которая практически не передвигает элементы.

Выбор шага изменения играет важную роль. Шелл предложил в своей первой работе значения 1, 2, 4, 8, 16, 32 и т.д. Однако при таком наборе до последнего прохода элементы с четными индексами никогда не сравниваются с элементами с нечетными индексами. Следовательно, при выполнении последнего прохода все еще возможны перемещения элементов на большие расстояния (например, такая ситуация возможна, когда элементы с меньшими значениями находятся в позициях с четными индексами, а элементы с большими значениями – в позициях с нечетными индексами).

В 1969 г. Дональд Кнут предложил последовательность 1, 4, 13, 40, 121 и т.д. (каждое следующее значение на единицу больше утроенного предыдущего). Для набора средних размеров такая последовательность позволяет получить достаточно высокие показатели быстродействия при несложном методе вычисления значений последовательности. На основе эмпирических исследований Кнут для среднего случая получил порядок O(n^5/4), а для худшего случая O(n^3/2). Именно такая последовательность используется в приведенной ниже реализации алгоритма.

{ Сортировка Шелла с применением ряда Кнута }

procedure ShellKnuthSort(aList: TList;

aFirst, aLast: Integer; aCompare: TCompareFunc);

var

i, j, h, N: Integer;