Сортировка слиянием

Begin

Begin

Begin

Var

Begin

Begin

Begin

Var

Begin

Begin

Var

Begin

Begin

Begin

Var

Begin

Const

D=...; { Максимальное количество цифр в числе }

P=...; { Основание системы счисления }

{ Возвращает значение n-ой цифры в числе v }

function Digit(v, n: Integer): Integer;

for n:=n downto 2 do

v:=v div P;

Digit:=v mod P;

end;

procedure Sort(var a: TA);

{ Индекс элемента, следующего за последним в i-ой группе }

b: array [0..P-2] of Integer;

i, j, k, m, x: Integer;

{ Перебор цифр, начиная с младшей }

for m:=1 to D do

{ Начальные значения индексов }

for i:=0 to P-2 do b[i]:=1;

{ Перебор массива }

for i:=1 to N do

{ Определение m-ой цифры }

k:=Digit(a[i],m);

x:=a[i];

{ Сдвиг - освобождение места в конце k-ой группы }

for j:=i downto b[k]+1 do

a[j]:=a[j-1];

{ Запись в конец k-ой группы }

a[b[k]]:=x;

{ Модификация k-го индекса и всех больших }

for j:=k to P-2 do

b[j]:=b[j]+1;

end;

end;

end;

Область памяти, занимаемая массивом, перераспределяется между входным и выходным множествами. Выходное множество размещается в начале массива и разбивается на группы. Разбиение отслеживается в массиве b. Элемент массива b[i] содержит индекс в массиве a, с которого начинается i+1-я группа. Номер группы определяется значением анализируемой цифры числа, поэтому индексация в массиве b начинается с 0.

Когда очередное число выбирается из входного множества и должно быть занесено в i-ю группу выходного множества, оно будет записано в позицию, определяемую значением b[i]. Но предварительно эта позиция должна быть освобождена: участок массива от b[i] до конца выходного множества включительно сдвигается вправо. После записи числа в i-ю группу i-е и все последующие значения в массиве b корректируются – увеличиваются на 1.

Результаты трассировки при P=10 и D=4 представлены в табл. 4.12.

Табл. 4.12. Трассировка цифровой сортировки.

Цифра	Содержимое массивов a и b
исх.	220 8390 9524 9510 462 2124 7970 4572 4418 1283
	220 8390 9510 7970 462 4572 1283 9524 2124 4418 ===========0========= ====2==== ==3== =====4===== ==8== b=(5,5,7,8,10,10,10,11,11)
	9510 4418 220 9524 2124 462 7970 4572 1283 8390 =====1===== ========2====== =6= ====7==== ==8== ==9== b=(1,3,6,6,6,6,7,9,10,11)
	2124 220 1283 8390 4418 462 9510 9524 4572 7990 ==1== ====2==== ==3== ====4==== ========5======== ==9== b=(1,2,4,5,7,10,10,10,10,11)
	220 462 1283 2124 4418 4572 7970 8390 9510 9524 ===0=== ==1== ==2== =====4==== ==7== ==8== =====9===== b=(3,4,5,5,7,7,7,8,9,11)

Быстрая сортировка Хоара относится к распределительным и обеспечивает показатели эффективности O(n·log₂(n)) даже при наихудшем исходном распределении. Алгоритм был разработан Хоаром в 1960 г. Алгоритм требует незначительной дополнительной памяти и относительно в реализации. Однако при реализации допускается много ошибок, которые могут остаться незамеченными и требовать дополнительного времени при выполнении, быстродействие в худшем случае может достигать показателя O(n²) и к тому же алгоритм относится к группе неустойчивых.

Тем не менее, сортировка Хоара в различных модификациях очень широко применяется. Во всех версиях Delphi методы TList.Sort и TStringList.Sort реализованы на основе быстрой сортировки. В C++ функция qsort из стандартной библиотеки времени выполнения также реализована на основе быстрой сортировки. Большое количество литературных источников по алгоритму быстрой сортировки позволяет корректно реализовать алгоритм и изучить многие особенности его работы.

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

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

Таким образом, для выполнения быстрой сортировки необходимо знать два алгоритма более низкого порядка: метод выбора базового элемента и метод эффективной перестановки элементов списка.

Лучшим случаем выбора базового элемента является медиана – средний элемент отсортированного списка. Тогда количество элементов в обоих подсписков будет одинаковым. Однако процесс поиска медианы сводится к алгоритму быстрой сортировки, поэтому неприемлем.

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

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

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

{ Быстрая сортировка Хоара с выбором

среднего элемента в качестве базового }

procedure QuickHoarStd1Sort(aList: TList;

aFirst, aLast: Integer; aCompare: TCompareFunc);

L, R: Integer;

M, Temp: Pointer;

if aFirst >= aLast then Exit;

{ В качестве базового элемента выбирается средний }

M:=aList.List^[(aFirst+aLast) div 2];

{ Начальные значения индексов }

L:=aFirst-1; R:=aLast+1;

{ Приступить к разбиению списка }

while True do

repeat Dec(R);

until aCompare(aList.List[R], M) <= 0;

repeat Inc(L);

until aCompare(aList.List[L], M) >= 0;

if L >= R then Break;

Temp:=aList.List[L];

aList.List[L]:=aList.List[R];

aList.List[R]:=Temp;

end;

{ Выполнить быструю сортировку левого подсписка }

QuickHoarStd1Sort(aList, aFirst, R, aCompare);

{ Выполнить быструю сортировку правого подсписка }

QuickHoarStd1Sort(aList, R+1, aLast, aCompare);

end;

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

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

Результаты трассировки приведены в табл. 4.13. В каждой строке таблицы показаны текущие положения индексов L и R, звездочками отмечены элементы, ставшие на свои места. Для каждого прохода показаны границы подмножества, в котором ведется сортировка.

Таблица 4.13. Трассировка сортировки Хоара.

Проход	Содержимое массива
	======================================= 42L 79 39 65 60 29 86 95 25 37R 37 79L 39 65 60 29 86 95 25 42R 37 42L 39 65 60 29 86 95 25R 79 37 25 39L 65 60 29 86 95 42R 79 37 25 39 65L 60 29 86 95 42R 79 37 25 39 42L 60 29 86 95R 65 79 37 25 39 42L 60 29 86R 95 65 79 37 25 39 42L 60 29R 86 95 65 79 37 25 39 29 60L 42R 86 95 65 79
	=============== 29L 25 39 37R 42* 60 86 95 65 79 29 25L 39 37R 42 60 86 95 65 79 29 25 37L 39R 42 60 86 95 65 79
	======= 25L 29R 37* 39 42 60 86 95 65 79
	== 25* 29 37* 39 42 60 86 95 65 79
	== 25* 29* 37* 39 42 60 86 95 65 79
	=================== 25* 29* 37* 39* 42* 60L 86 95 65 79R 25* 29* 37* 39* 42* 60L 86 95 65L 79 25* 29* 37* 39* 42* 60L 86 95L 65 79 25* 29* 37* 39* 42* 60L 86R 95 65 79
	=============== 25* 29* 37* 39* 42* 60* 79L 95 65 86R 25* 29* 37* 39* 42* 60* 79L 86 65R 95 25* 29* 37* 39* 42* 60* 65 86L 79R 95
	== 25* 29* 37* 39* 42* 60* 65 79* 86 95
	======= 25* 29* 37* 39* 42* 60* 65* 79* 86L 95R
	== 25* 29* 37* 39* 42* 60* 65* 79* 86* 95

Незначительная модификация алгоритма позволит избавиться от одного рекурсивного вызова. В следующем примере используется цикл while совместно с изменением значения переменной aFirst. В результате левые подсписки будут обрабатываться рекурсивно, а правые – итеративно.

{ Быстрая сортировка Хоара (без одной рекурсии) }

procedure QuickHoarStd2Sort(aList: TList;

aFirst, aLast: Integer; aCompare: TCompareFunc);

L, R: Integer;

M, Temp: Pointer;

{ Повторять, по в списке

есть хотя бы два элемента }

while (aFirst < aLast) do

{ В качестве базового элемента выбирается средний }

M:=aList.List^[(aFirst+aLast) div 2];

{ Начальные значения индексов }

L:=aFirst-1; R:=aLast+1;

{ Приступить к разбиению списка }

while True do

repeat Dec(R);

until aCompare(aList.List[R], M) <= 0;

repeat Inc(L);

until aCompare(aList.List[L], M) >= 0;

if L >= R then Break;

Temp:=aList.List[L];

aList.List[L]:=aList.List[R];

aList.List[R]:=Temp;

end;

{ Выполнить быструю сортировку левого подсписка }

if aFirst < R then

QuickHoarStd2Sort(aList, aFirst, R, aCompare);

{ Выполнить быструю сортировку правого подсписка и устранение рекурсии }

aFirst:=R+1;

end;

end;

Другая незначительная модификация состоит в выборе базового элемента случайным образом: случайно выбранный элемент меняется местом со средним и становится базовым. При наличии хорошего генератора псевдослучайных чисел вероятность попадания на худший случай (граничное значение) становится пренебрежимо мало. Заметим, однако, что понижение вероятности не повышает скорость выполнения алгоритма в целом. Пример реализации алгоритма со случайным выбором базового элемента приведен ниже.

{ Быстрая сортировка Хоара со случайным выбором базового элемента }

procedure QuickHoarRNDSort(aList: TList;

aFirst, aLast: Integer; aCompare: TCompareFunc);

L, R: Integer;

M, Temp: Pointer;

while aFirst < aLast do

{ Начало добавляемой части }

{ Выбрать случайный элемент, переставить его со

средним элементом и взять в качестве базового }

R:=aFirst + Random(aLast - aFirst + 1);

L:=(aFirst + aLast) div 2;

M:=aList.List[R];

aList.List[R]:=aList.List[L];

aList.List[L]:=M;

{ Конец добавляемой части }

L:=aFirst-1;

R:=aLast+1;

while True do

repeat Dec(R);

until aCompare(aList.List[R], M) <= 0;

repeat Inc(L);

until aCompare(aList.List[L], M) >= 0;

if L >= R then Break;

Temp:=aList.List[L];

aList.List[L]:=aList.List[R];

aList.List[R]:=Temp;

end;

if (aFirst < R) then

QuickHoarRNDSort(aList, aFirst, R, aCompare);

aFirst:=R+1;

end;

end;

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

Алгоритмы сортировки слиянием привлекают простотой и наличием важных особенностей: они имеют порядок O(n·log₂n), не имеют худших случаев, допускают сортировку содержимого файлов, размер которых слишком велик для полного размещения в памяти.

Для пояснения алгоритма сортировки поясним сначала принцип слияние. Пусть имеются два отсортированных в порядке возрастания массива p[1], p[2],..., p[n] и q[1], q[2],..., q[n] и имеется пустой массив r[1], r[2],..., r[2n], который требуется заполнить значениями массивов p и q в порядке возрастания.

Для слияния выполняются следующие действия: сравниваются p[1] и q[1], и меньшее из значений записывается в r[1]. Предположим, это значение p[1]. Тогда p[2] сравнивается с q[1] и меньшее из значений заносится в r[2]. Предположим, это значение q[1]. Тогда на следующем шаге сравниваются значения p[2] и q[2] и т.д., пока не будет достигнута граница одного из массивов. Тогда остаток другого массива просто дописывается в конец результирующего массива r.

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

Время выполнения алгоритма двухпутевого слияния зависит от количества элементов в обоих массивах. Если в первом находится n элементов, а во втором – m, то в худшем случае потребуется (n+m) сравнений. Следовательно, алгоритм двухпутевого слияния принадлежит к классу O(n). Пример слияния двух массивов показан на рис. 4.2.

На основе алгоритма двухпутевого слияния можно прийти к рекурсивному определению сортировки слиянием: исходный массив следует разделить на две половины, применить к каждой половине алгоритм сортировки слиянием, а затем с помощью алгоритма двухпутевого слияния объединить подсписки в один отсортированный массив. Рекурсивные вызовы завершаются, когда подсписок n-ого уровня, переданный алгоритму сортировки, будет содержать всего один элемент, поскольку он, очевидно, уже отсортирован.

Сортировка слиянием обладает единственным недостатком – требуется наличие третьего списка, в котором будут храниться результаты слияния. Размер требуемой дополнительной памяти составляет до половины размера исходно массива.

Дата добавления: 2014-01-07