Разработка алгоритма сортировки прямым выбором

Алгоритм сортировки прямым выбором в некотором смысле противоположен сортировке прямыми включениями.

При прямом включении на каждом шаге рассматривается только один очередной элемент входной последовательности и все элементы готовой последовательности для нахождения места включения.

При прямом выборе для поиска одного элемента с наименьшим ключом просматриваются все элементы входной последовательности и найденный элемент помещается как очередной элемент в конец готовой последовательности.

Метод сортировки прямым выбором основан на следующих правилах:

· Выбирается элемент с наименьшим ключом.

· Он меняется местами с первым элементом a₀.

· Затем эти операции повторяются с оставшимися n-1 элементами, n-2 элементами и так далее до тех пор, пока не останется один, самый большой элемент.

Таблица 1

0, 57	-0, 11	0, 27	0, 48	0, 05	-24	0, 09	1, 46	-0, 39	-1, 00
-24	-0, 11	0, 27	0, 48	0, 05	0, 57	0, 09	1, 46	-0, 39	-1, 00
-24	-1, 00	0, 27	0, 48	0, 05	0, 57	0, 09	1, 46	-0, 39	-0, 11
-24	-1, 00	-0, 39	0, 48	0, 05	0, 57	0, 09	1, 46	0, 27	-0, 11
-24	-1, 00	-0, 39	-0, 11	0, 05	0, 57	0, 09	1, 46	0, 27	0, 48
-24	-1, 00	-0, 39	-0, 11	0, 05	0, 57	0, 09	1, 46	0, 27	0, 48
-24	-1, 00	-0, 39	-0, 11	0, 05	0, 09	0, 57	1, 46	0, 27	0, 48
-24	-1, 00	-0, 39	-0, 11	0, 05	0, 09	0, 27	1, 46	0, 57	0, 48
-24	-1, 00	-0, 39	-0, 11	0, 05	0, 09	0, 27	0, 48	0, 57	1, 46
-24	-1, 00	-0, 39	-0, 11	0, 05	0, 09	0, 27	0, 48	0, 57	1, 46
-24	-1, 00	-0, 39	-0, 11	0, 05	0, 09	0, 27	0, 48	0, 57	1, 46
-24	-1, 00	-0, 39	-0, 11	0, 05	0, 09	0, 27	0, 48	0, 57	1, 46
-24	-1, 00	-0, 39	-0, 11	0, 05	0, 09	0, 27	0, 48	0, 57	1, 46

Алгоритм сортировки прямым выбором

Блок-схема 1. Процедура сортировки массива методом прямого выбора.

Прямой выбор

j, A, i

A[i], A[j]

Findmin

Swap

Input N, A[1..N]

j: =0 to N-1

Swap

Input i, j

t: =i

i: =j

j: =t

A[u]< min

Findmin

Input j, A, i

u: =j+1 to N-1

i: =j, min: =A[j]

min: =A[u]

i: =u

нет

да

Текст процедуры для сортировки прямым выбором

procedure FindMin(startindex: integer; M: ar; var lowindex: integer); {Перебирает массив начиная с заданного индекса и находим минимальный элемент}

var min, u: integer;

Begin

lowindex: = startindex;

min: = M[startindex];

for u: =startindex+1 to N-1 do

Begin

inc(Psrav);

if M[u]< min then

Begin

min: = M[u];

lowindex: = u;

end;

…

procedure swap( var x, y, z: integer); {Меняем местами заданные элементы массива}

var t: integer;

Begin

t: = x;

x: = y;

y: = t;

inc(z);

end;

…

procedure Pryamoi_vibor(M: Ar); {Сортирует массив с помощью прямого выбора}

Var

j: integer;

Begin

for j: =0 to N-1 do

Begin

FindMin(j, m, i);

swap(M[j], M[i], Pper);

End

end;

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

Разработка алгоритма шейкерной сортировки

Шейкерная сортировка − разновидность пузырьковой сортировки. Отличается тем, что просмотры элементов выполняются один за другим в противоположных направлениях, при этом большие элементы стремятся к концу массива, а маленькие - к началу. Своим появлением эта сортировка обязан такому недостатку сортировки «пузырьком», при котором «лёгкие пузырьки» всплывают за один проход, а «тяжёлые» − тонут за несколько. Такая ассиметрия и вызвала появление новой сортировки, на каждом шаге которой осуществляется проход как в одну сторону, так и в другую. Таким образом, на каждом шаге «лёгкий пузырёк» всплывает на поверхность, а «тяжёлый» − тонет.

Метод этот получил название шейкерной сортировки.

Таблица 2

Шаг	Направление движения	Элементы массива

	Справа-налево
Слева-направо	10 \|\|
	Справа-налево	10 \|\|				\|\| 75
Слева-направо		17 \|\|			\|\| 75
	Справа-налево		17 \|\|		\|\| 70
Слева-направо			18 \|\|	\|\| 70

Серым цветом в таблице выделена та часть массива, которая исключается из просмотра.

Алгоритм шейкерной сортировки

Блок-схема 2. Процедура шейкерной сортировки массива.

l: =2; r: =N-1; k: =R

Input A[N]

Шейкер

A2 j: =r downto l-1

a[j-1] > a[j]

нет

да

A3 j: =l to r

A[j-1] > A[j]

нет

да

r: =k-1

A1 l> r

L: =k+1

A[j], A[j-1]

Swap

k: =j

A[j], A[j-1]

k: =j

Swap

Текст процедуры шейкерной сортировки

procedure Shaker(M: Ar); {Сортирует массив методом смешивания}

Var

j, k, l, r: integer;

Begin

L: =2;

R: =N-1;

k: =R;

Repeat

Begin

for j: =r downto l-1 do

Begin

if M[j-1] > M[j] then

Begin

swap(M[j], M[j-1], Sper);

k: =j;

end;

inc(Ssrav);

end;

L: =k+1;

for j: =l to r do

Begin

if M[j-1]> M[j] then

Begin

swap(M[j], M[j-1], Sper);

k: =j;

end;

inc(Ssrav);

end;

r: =k-1;

end;

until L> R;

end;

Быстрая сортировка

Разработка алгоритма быстрой сортировки

Быстрая сортировка, часто называемая qsort по имени реализации в стандартной библиотеке языка Си — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром. Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении n элементов). Этот улучшенный метод сортировки основан на обмене.

Если количество элементов в массиве не многим меньше максимального их значения, то в данном случае наиболее эффективным и по быстродействию, и по простоте является быстрая сортировка. Основные достоинства этого алгоритма состоят в том, что он точечный (использует лишь небольшой дополнительный стек), в среднем требует только около N log N операций для того, чтобы отсортировать N элементов, и имеет экстремально короткий внутренний цикл. Недостатки алгоритма состоят в том, что он рекурсивен (реализация очень затруднена когда рекурсия недоступна), в худшем случае он требует N2 операций, кроме того он очень " хрупок": небольшая ошибка в реализации, которая легко может пройти незамеченной, может привести к тому, что алгоритм будет работать очень плохо на некоторых файлах.

Основная идея алгоритма быстрой сортировки состоит в том, что случайным образом выбирается некоторый элемент массива x, после чего массив просматривается слева, пока не встретится элемент a[i] такой, что a[i] > x, а затем массив просматривается справа, пока не встретится элемент a[j] такой, что a[j] < x. Эти два элемента меняются местами, и процесс просмотра, сравнения и обмена продолжается, пока мы не дойдем до элемента x. В результате массив окажется разбитым на две части - левую, в которой значения ключей будут меньше x, и правую со значениями ключей, большими x.

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

Таблица 3

Начальное состояние массива	8 23 5 65 44 33 1 6
Шаг 1. (в качестве x выбирается a[4])	8 23 5 65 44 33 1 6 \|-------------\| 8 23 5 6 44 33 1 65
Шаг 2. (в подмассиве a[1..7] за x выбирается a[4])	8 23 5 6 44 33 1 65 \|-------------------\| 1 23 5 6 44 33 8 65 \|-----\| 1 6 5 23 44 33 8 65
Шаг 3. (в подмассиве a[1..3] в качестве x выбирается a[2])	1 6 5 23 44 33 8 65 \|--\| 1 5 6 23 44 33 8 65
Шаг 4. (в подмассиве a[4..7] в качестве x выбирается a[5])	1 5 6 23 44 33 8 65 \|-----\| 1 5 6 23 8 33 44 65
Шаг 5. (в подмассиве a[4..6] в качестве x выбирается a[5])	1 5 6 23 8 33 44 65 \|---\| 1 5 6 8 23 33 44 65

Алгоритм быстрой сортировки массива.

Блок-схема 3. Процедура быстрой сортировки массива

QSort

i: =L, j: =R

A1i> j

Qsort

A[N], L, R

i < = j

w: =A[(L+R)div 2]

A2 A[i]< w

inc(i)

A3 w < A[j]

dec(j)

A[i], A[j]

inc(i), dec(j)

Swap

L < j

i < R

L, j

I, R

QSort

да

нет

да

Текст процедуры быстрой сортировки

procedure Qsort(l, r: integer); {Сортирует массив Быстрой сортировкой}

var i, j, w: integer;

Begin

i: = l; j: = r;

w: = Q[(l+r) div 2];

Repeat

while (Q[i] < w) do begin inc(i); inc(Qsrav); end;

while (w < Q[j]) do begin dec(j); inc(Qsrav); end;

if (i < = j) then

Begin

swap(Q[i], Q[j], Qper);

inc(i); dec(j);

end;

until (i > j);

if (l < j) then qSort(l, j);

if (i < r) then qSort(i, r);

end;

Графическая работа

Для того, чтобы изобразить гистограммы и таблицы по полученным данным, воспользуемся процедурами из модулей GraphABC и ABCobjects.

Готовый алгоритм построения гистограмм для значений из массива Q выглядит следующим образом:

Procedure Gist; {Строит гистрограмму одного массива}

Var

a, c, b: integer;

x: real;

Begin

SetBrushColor(clgreen);

Textout(500, 5, 'Быстрая');

SetBrushColor(clDarkOrchid);

Textout(600, 5, 'Прямая');

SetBrushColor(clHotPink);

Textout(700, 5, 'Шейкерная');

SetBrushColor(clmoneygreen);

Textout(95, a+55, 'Перемещений');

Textout(355, a+55, 'Сравнений');

Textout(605, a+55, 'Время в мсек.');

x: =Qper;

If x< Pper then x: =Pper;

If x< Sper then x: =Sper;

a: =round(90/(x/Qper));

b: =round(90/(x/Pper));

c: =round(90/(x/Sper));

SetBrushColor(clgreen);

FillRectangle(10, y+165, 70, y+165-a+2);

SetBrushColor(clDarkOrchid);

FillRectangle(100, y+165, 160, y+165-b+2);

SetBrushColor(clHotPink);

FillRectangle(190, y+165, 250, y+165-c+2);

x: =Qsrav;

If x< Psrav then x: =Psrav;

If x< Ssrav then x: =Ssrav;

a: =round(90/(x/Qsrav));

b: =round(90/(x/Psrav));

c: =round(90/(x/Ssrav));

SetBrushColor(clgreen);

FillRectangle(280, y+165, 340, y+165-a+2);

SetBrushColor(clDarkOrchid);

FillRectangle(370, y+165, 430, y+165-b+2);

SetBrushColor(clHotPink);

FillRectangle(460, y+165, 520, y+165-c+2);

x: =Qtime;

If x< Ptime then x: =Ptime;

If x< Stime then x: =Stime;

a: =round(90/(x/Qtime));

b: =round(90/(x/Ptime));

c: =round(90/(x/Stime));

SetBrushColor(clgreen);

FillRectangle(550, y+165, 610, y+165-a+2);

SetBrushColor(clDarkOrchid);

FillRectangle(640, y+165, 700, y+165-b+2);

SetBrushColor(clHotPink);

FillRectangle(730, y+165, 790, y+165-c+2);

setpencolor(clblack);

SetBrushColor(clmoneygreen);

Textout(10, y+185, inttostr(Qper));

Textout(100, y+185, inttostr(Pper));

Textout(190, y+185, inttostr(Sper));

Textout(280, y+185, inttostr(Qsrav));

Textout(370, y+185, inttostr(Psrav));

Textout(460, y+185, inttostr(Ssrav));

str(Qtime: 8: 4, Qtimest);

str(Ptime: 8: 4, Ptimest);

str(Stime: 8: 4, Stimest);

Textout(550, y+185, Qtimest);

Textout(640, y+185, Ptimest);

Textout(730, y+185, Stimest);

end;

⇐ Предыдущая 123 4 Следующая ⇒