ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 23.01.2025
Просмотров: 3155
Скачиваний: 3
Результаты трассировки приведены в табл. 4.13. В каждой строке таблицы показаны текущие положения индексов L и R, звездочками отмечены элементы, ставшие на свои места. Для каждого прохода показаны границы подмножества, в котором ведется сортировка.
Таблица 4.13. Трассировка сортировки Хоара.
|
Проход |
Содержимое массива |
|
1 |
======================================= 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 |
|
2 |
=============== 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 |
|
3 |
======= 25L 29R 37* 39 42 60 86 95 65 79 |
|
4 |
== 25* 29 37* 39 42 60 86 95 65 79 |
|
5 |
== 25* 29* 37* 39 42 60 86 95 65 79 |
|
6 |
=================== 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 |
|
7 |
=============== 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 |
|
8 |
== 25* 29* 37* 39* 42* 60* 65 79* 86 95 |
|
9 |
======= 25* 29* 37* 39* 42* 60* 65* 79* 86L 95R |
|
10 |
== 25* 29* 37* 39* 42* 60* 65* 79* 86* 95 |
Незначительная модификация алгоритма позволит избавиться от одного рекурсивного вызова. В следующем примере используется цикл while совместно с изменением значения переменной aFirst. В результате левые подсписки будут обрабатываться рекурсивно, а правые – итеративно.
{ Быстрая сортировка Хоара (без одной рекурсии) }
procedure QuickHoarStd2Sort(aList: TList;
aFirst, aLast: Integer; aCompare: TCompareFunc);
var
L, R: Integer;
M, Temp: Pointer;
begin
{ Повторять, по в списке
есть хотя бы два элемента }
while(aFirst<aLast)do
begin
{ В качестве базового элемента выбирается средний }
M:=aList.List^[(aFirst+aLast) div 2];
{ Начальные значения индексов }
L:=aFirst-1; R:=aLast+1;
{ Приступить к разбиению списка }
whileTruedo
begin
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);
var
L, R: Integer;
M, Temp: Pointer;
begin
while aFirst < aLast do
begin
{ Начало добавляемой части }
{ Выбрать случайный элемент, переставить его со
средним элементом и взять в качестве базового }
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
begin
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·log2n), не имеют худших случаев, допускают сортировку содержимого файлов, размер которых слишком велик для полного размещения в памяти.
Для пояснения алгоритма сортировки поясним сначала принцип слияние. Пусть имеются два отсортированных в порядке возрастания массива 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-ого уровня, переданный алгоритму сортировки, будет содержать всего один элемент, поскольку он, очевидно, уже отсортирован.
Сортировка слиянием обладает единственным недостатком – требуется наличие третьего списка, в котором будут храниться результаты слияния. Размер требуемой дополнительной памяти составляет до половины размера исходно массива.
Пример реализации алгоритма приведен ниже. Помимо известных параметров процедура требует передачи указателя на временный массив, который будет использоваться для выполнения процедуры слияния.
{ Сортировка слиянием }
procedure MSS(aList: TList; aFirst, aLast: Integer;
aCompare: TCompareFunc; aTempList: PPointerList);
var
Mid, i, j, ToInx,
FirstCount: Integer;
begin
{ Вычислить среднюю точку }
Mid:=(aFirst + aLast) div 2;
{ Рекурсивная сортировка слиянием первой и второй половин списка }
if aFirst < Mid then
MSS(aList, aFirst, Mid, aCompare, aTempList);
if (Mid+1) < aLast then
MSS(aList, Mid+1, aLast, aCompare, aTempList);
{ Скопировать первую половину списка во вспомогательный список }
FirstCount:=Mid-aFirst+1;
Move(aList.List[aFirst], aTempList[0], FirstCount*SizeOf(Pointer));
{ Установить значения индексов: i - индекс для вспомогательного списка
(т.е. первой половины); j - индекс для второй половины списка;
ToInx - индекс в результирующем списке, куда будут копироваться
отсортированные элементы }
i:=0; j:=Mid+1; ToInx:=aFirst;
{ Выполнить слияние двух списков; повторять
пока один из списков не опустеет }
while (i < FirstCount) and (j <= aLast) do
begin
{ Определить элемент с наименьшим значением из следующих
элементов в обоих списках и скопировать его; увеличить
значение соответствующего индекса }
if aCompare(aTempList[i], aList.List[j]) <= 0 then
begin
aList.List[ToInx]:=aTempList[i];
Inc(i);
end
else
begin
aList.List[ToInx]:=aList.List[j];
Inc(j);
end;
{ В объединенных списках есть еще один элемент }
Inc(ToInx);
end;
{ Если в первом подсписке остались элементы, скопировать их }
if i < FirstCount then
Move(aTempList[i], aList.List[ToInx], (FirstCount - i)*SizeOf(Pointer));
{ Если во втором списке остались элементы, то они уже находятся в нужных