Шейкерная

Прямого выбора

Алгоритм сортировки массива по возрастанию методом прямого выбора может быть представлен так:

1. Просматривая массив от первого элемента, найти минимальный элемент и поместить его на место первого элемента, а первый — на место минимального.

2. Просматривая массив от второго элемента, найти минимальный элемент и поместить его на место второго элемента, а второй — на место минимального.

3. И так далее до предпоследнего элемента.

Пример

5, 13, 3, 4

3, 13, 5, 4

3, 4, 5, 13 и тд…

……..

begin

for i: = 1 to 9 do

for j: = i + 1 to 10 do

if s[i] < s[j] then

begin

g: = s[i];

s[i]: = s[j];

s[j]: = g;

end;

end;

………

Прямого обмена(пузырек)

program xxx;

const n=5;

var a: array[1..n] of integer;

buff, i: integer;

ischange: boolean;

begin

randomize;

for i: =1 to n do

a[i]: =random(11);

ischange: =true;

while ischange do

begin

ischange: =false;

for i: =1 to n-1 do

begin

if a[i]> a[i+1] then

begin

buff: =a[i];

a[i]: =a[i+1];

a[i+1]: =buff;

ischange: =true;

end;

end;

end;

for i: =1 to n do

write(a[i], ' ');

end.

Гномья сортировка

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

Пример

5, 13, 3, 4

5, 3, 13, 4

3, 5, 13, 4

3, 5, 4, 13 и тд…

………….

begin

i: = 2;

j: = 3;

while i < = n do

begin

if a[i-1] < = a[i] then

begin

i: = j;

j: = j + 1

end

else

begin

l: = a[i-1];

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

a[i]: = l;

i: = i - 1;

if i = 1 then

begin

i: = j;

j: = j + 1

end;

end;

end;

end;

…………

Шейкерная

разновидность пузырьковой сортировки. Анализируя метод пузырьковой сортировки можно отметить два обстоятельства.

Во-первых, если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована и, следовательно, ее можно исключить из рассмотрения.

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

Эти две идеи приводят к следующим модификациям в методе пузырьковой сортировки. Границы рабочей части массива (т.е. части массива, где происходит движение) устанавливаются в месте последнего обмена на каждой итерации. Массив просматривается поочередно справа налево и слева направо.

Пример

Образно алгоритм можно описать так: на каждом шаге основного цикла рассматривается массив a[Left]÷ a[Right], после выполнения двух внутренних циклов минимальный и максимальный елемент в исходном массиве перетекают к краям, минимальный в — a[Left], максимальный — в a[Right]. Пусть максимальный елемент имеет индекс k, тогда массив можно изобразить так: a[Left], a[1],.., a[k-1], A[k], a[k+1],.., a[Right]; После сравнения A[k] с a[k+1] значение A[k] перейдет в k+1-ую ячейку, после сравнения k+1-ой c k+2-ой – в k+2-eю, и так далее, пока он не сместится в крайне правое положение с индексом Right. Аналогично для минимального. После выполнения цикла по всем подмассивам он отсортируется

program Shaker;

var A: array[1..100] of integer;

N, i, k, x, j, d: integer;

begin

write('количество элементов массива');

read(N);

for i: =1 to n do A[i]: =random(10);

d: =1; i: =0;

for k: =n-1 downto 1 do { k – количество сравниваемых пар }

begin

i: =i+d;

for j: =1 to k do

begin

if (A[i]-A[i+d])*d> 0 then

{меняем местами соседние элементы}

begin x: =A[i]; A[i]: =A[i+d]; A[i+d]: =x; end;

i: =i+d;

end;

d: =-d;

{меняем направление движения на противоположное}

end;

for i: =1 to n do write(A[i], ' '); {вывод массива}

end.