Дополнительно о сортировках

Begin

Begin

Begin

Begin

Begin

Whiletrue do

Begin

Var

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

Begin

Begin

Begin

Begin

Repeat

Begin

Var

Шейкерная сортировка

Данная сортировка есть улучшенный вариант сортировки методом пузырька.

На первом полу шаге проверяются (справа налево) все пары соседних элементов массива, начиная с последней. Если пара «неправильная» (левый элемент больше правого), производится обмен значениями в паре. Наименьший из всех элементов массива, если только он не стоял на первом месте, «просочится» в результате первого шага на первую позицию, поскольку он будет «неправильно» расположен относительно каждого из своих соседей слева. Вместе с тем, может оказаться и так, что первый элемент изначально был минимальным. Более того, может оказаться так, что первые k элементов изначально занимали подобающие им места, поскольку были наименьшими и стояли в порядке возрастания. Признаком такой ситуации может послужить то, что первые k элементов не участвовали в обмене. Следовательно, последующая сортировка должна затронуть только элементы массива с номерами большими, чем k. Переменная L (после изменения оператором L:=k+1) имеет смысл левой границы неотсортированной пока части массива.

На втором полу шаге проверяются (теперь слева направо) все пары соседних элементов массива, начиная с (L-1)–ой. Если последние k элементов изначально занимали подобающие им места, поскольку были наибольшими и стояли в порядке возрастания, переменная R (после изменения оператором R:=k-1) будет содержать информацию о правой границе неотсортированной пока части массива.

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

Шейкерная сортировка, увы, работает несколько хуже сортировки методом прямого выбора.

procedure ShakerSort;

j,k,L,R: integer;

x,y: single;

nMove:=0;

nCompare:=0;

L:=2; R:=nCurr; k:=nCurr;

for j:=R downto L do

x:=A[j-1]; y:=A[j];

nMove:=nMove+2;

nCompare:=nCompare+1;

if x>y then

A[j-1]:=y; A[j]:=x;

k:=j;

nMove:=nMove+2;

end;

end;

L:=k+1;

for j:=L to R do

x:=A[j-1]; y:=A[j];

nMove:=nMove+2;

nCompare:=nCompare+1;

if x>y then

A[j-1]:=y; A[j]:=x;

k:=j;

nMove:=nMove+2;

end;

end;

R:=k-1;

until L>R;

end;

procedure ShellSort;

i, j, k, L, m, nSteps: integer;

x: Single;

mSteps: array of integer;

nSteps:= 1;

i:= 1;

SetLength(mSteps, nSteps);

mSteps[nSteps - 1]:= i;

i:= 3 * i + 1;

if 3 * i >= nCurr then break;

Inc(nSteps);

SetLength(mSteps, nSteps);

mSteps[nSteps - 1]:= i;

end;

nCompare:= 0;

nMove:= 0;

for m:= nSteps downto 1 do

k:= mSteps[m - 1];

for L:= 1 to k do

i:= L + k;

while i <= nCurr do

x:= A[i];

Inc(nMove);

j:= i;

while (j > k) and (x < A[j - k]) do

Inc(nCompare);

A[j]:= A[j - k];

Inc(nMove, 2);

j:= j - k;

end;

if j > k then Inc( nCompare);

A[j]:= x;

Inc(nMove);

i:= i + k;

end;

end;

end;

end;

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

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