End else

Begin

Begin

Begin

Begin

Begin

Begin

Var

Begin

Begin

Begin

Var

Begin

Begin

Begin

Var

Begin

Begin

Var

Begin

Begin

Begin

Begin

Var

Begin

Begin

Begin

Begin

Begin

Var

Begin

Begin

Begin

Begin

Var

Begin

Begin

Begin

Var

Begin

Begin

Begin

Begin

Var

Begin

Begin

Begin

Var

Begin

Begin

Begin

Begin

Var

Begin

Begin

Var

Implementation

{ Сортировка простой выборкой }

procedure SelectionStdSort;

i, j, m, N: Integer;

{ Состояние элементов входного множества}

c: array of Boolean;

N:=aList.Count;

SetLength(c, N);

{ Сброс отметок}

for i:=0 to N-1 do c[i]:=True;

{ Поиск первого невыбранного элемента во входном множестве}

for i:=0 to N-1 do

j:=0;

while not c[j] do j:=j+1;

m:=j;

{ Поиск минимального элемента }

for j:=1 to N-1 do

if c[j] and (aCompare(aList.List[j], aList.List[m]) = -1) then m:=j;

{ Запись в выходное множество}

bList.Items[i]:=aList.List[m];

{ В входное множество - "пусто" }

c[m]:=False;

end;

end;

{ Обменная сортировка простой выборкой }

procedure SelectionSort;

i, j, IndexOfMin: Integer;

Temp: Pointer;

{ Перебор элементов выходного множества }

for i:=aFirst to pred(aLast) do

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

IndexOfMin:=i;

{ Поиск минимума во входном множестве }

for j:=i+1 to aLast do

{ Обмен первого элемента входного множества с минимальным }

if (aCompare(aList.List[j], aList.List[IndexOfMin]) < 0) then

IndexOfMin:=j;

Temp:=aList.List[i];

aList.List[i]:=aList.List[IndexOfMin];

aList.List[IndexOfMin]:=Temp;

end;

end;

{ Сортировка простыми вставками }

procedure InsertionStdSort;

var i, j, k: Integer;

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

for i:=0 to aList.Count-1 do

j:=0;

{ Поиск места для a[i] в выходном массиве

при условии (j < i) и (b[j] <= a[i]) }

while (j < i) and (aCompare(bList.Items[j],aList.Items[i]) <= 0) do

j:=j+1;

{ Освобождение места для нового элемента }

for k:=i downto j+1 do

bList.Items[k]:=bList.Items[k-1];

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

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

end;

end;

{ Сортировка методом вставок }

procedure InsertionBublSort;

i, j: Integer;

Temp: Pointer;

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

for i:=aFirst+1 to aLast do

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

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

Temp:=aList.List[i];

j:=i;

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

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

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

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

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

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

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

Dec(j);

end;

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

aList.List[j]:=Temp;

end;

end;

{ Оптимизированная сортировка методом вставок }

procedure InsertionOptSort;

i, j, IndexOfMin: Integer;

Temp: Pointer;

{ Найти наименьший элемент и поместить его в первую позицию }

IndexOfMin:=aFirst;

for i:=aFirst+1 to aLast do

if (aCompare(aList.List[i], aList.List[IndexOfMin]) < 0) then

IndexOfMin:=i;

if aFirst <> IndexOfMin then

Temp:=aList.List[aFirst];

aList.List[aFirst]:=aList.List[IndexOfMin];

aList.List[IndexOfMin]:=Temp;

end;

{ Сортировка методом простых вставок }

for i:=aFirst+2 to aLast do

Temp:=aList.List[i];

j:=i;

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

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

Dec(j);

end;

aList.List[j]:=Temp;

end;

end;

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

procedure BubbleSort;

i,j: Integer;

Temp: Pointer;

Done: Boolean;

for i:=aFirst to aLast-1 do

Done:=True;

for j:=aLast downto i+1 do

{ Переставить j-й и j-1-й элементы }

if aCompare(aList.List[j],aList.List[j-1]) < 0 then

Temp:=aList.List[j];

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

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

Done:=False;

end;

if Done then Exit;

end;

end;

{ Пузырьковая двухпроходная сортировка }

procedure ShakerSort;

i: Integer;

Temp: Pointer;

while aFirst < aLast do

for i:=aLast downto aFirst+1 do

if aCompare(aList.List[i], aList.List[i-1]) < 0 then

Temp:=aList.List[i];

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

aList.List[i-1]:=Temp;

end;

Inc(aFirst);

for i:=aFirst+1 to aLast do

if aCompare(aList.List[i], aList.List[i-1]) < 0 then

Temp:=aList.List[i];

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

aList.List[i-1]:=Temp;

end;

Dec(aLast);

end;

end;

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

procedure ShellSort;

h, i, N: Integer;

Temp: Pointer;

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

k: Boolean;

N:=aList.Count;

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

h:=N div 2;

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

while h > 0 do

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

k:=True;

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

while k do

k:=False;

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

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

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

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

Temp:=aList.List[i];

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

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

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

k:=True;

end;

end;

end;

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

h:=h div 2;

end;

end;

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

procedure ShellKnuthSort;

i, j, h, N: Integer;

Temp: Pointer;

{ Начальное значение h должно быть

близко к 1/9 количества элементов }

h:=1; N:=(aLast - aFirst) div 9;

while h <= N do

h:=h*3 + 1;

{ При каждом проходе цикла значение

шага уменьшается на треть }

while h > 0 do

{ Выполнить сортировку методом

вставки для каждого подмножества }

for i:=(aFirst + h) to aLast do

Temp:=aList.List[i];

j:=i;

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

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

Dec(j, h);

end;

aList.List[j]:=Temp;

end;

h:=h div 3;

end;

end;

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

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

procedure QuickHoarStd1Sort;

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;

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

procedure QuickHoarStd2Sort;

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;

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;

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

базового элемента методом трех медиан }

procedure QuickHoarMDNSort;

L, R: Integer;

M, Temp: Pointer;

while aFirst < aLast do

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

{ Если в списке есть, по крайней мере, три элемента,

выбрать базовый элемент как медиану первого, последнего

и среднего элементов и записать его в позицию в середину списка }

if aLast - aFirst >= 2 then

R:=(aFirst + aLast) div 2;

if aCompare(aList.List[aFirst], aList.List[R]) > 0 then

Temp:=aList.List[aFirst];

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

aList.List[R]:=Temp;

end;

if aCompare(aList.List[aFirst], aList.List[aLast]) > 0 then

Temp:=aList.List[aFirst];

aList.List[aFirst]:=aList.List[aLast];

aList.List[aLast]:=Temp;

end;

if aCompare(aList.List^[R], aList.List[aLast]) > 0 then

Temp:=aList.List[R];

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

aList.List[aLast]:=Temp;

end;

M:=aList.List[R];

{ В противном случае в списке всего два

элемента, выбрать в качестве базового первый }

M:=aList.List[aFirst];

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

L:=aFirst-1;

R:=aLast+1;

while True do

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