Обработка одномерных массивов (сортировка)

Фрагмент программы, реализующей сортировку массива методом вставки.

For i:=1 to n do

Begin

x:=y[i];{Сохраним текущий элемент массива.}

{В переменной j будем хранить номера элементов, предшествующих текущему.}

J:=i-1;

{Сдвиг массива на одну позицию в право до тех пор, пока}

While (x0) do

Begin

y[j+1] :=y[j]:

j:=j-1;

End;

{Запись текущего элемента на соответствующую позицию,}

{то есть перед элементами, превышающими его.}

y[j+1]:=x;

end;

Сортировка массива по возрастанию методом «выбора»

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

Для упорядочивания массива по убыванию необходимо перемещать минимальный элемент.

max max=y[i] nom=i " width="640"

Блок – схема сортировки массива методом «выбора»

K=n

j=1,n

n=n-1

max=y[1]

nom=1

b=y[nom]

y[nom]=y[n]

y[n]=b

i=2,n

y[i]max

max=y[i]

nom=i

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

Принцип работы

Один из самых быстрых алгоритмов, позволяющих достигать производительности ~ O(n*log n).

1. В исходной последовательности выбирается некоторый опорный элемент a[i].

2. Пробегаемся по всей последовательности и элементы, меньшие, либо равные a[i] располагаем слева от него, большие - справа.

• Эту же самую процедуру рекурсивно запускаем для 2-х полученных половинок. =a[i]

Т.е. в 2-х полученных последовательностях слева и справа от выбранного на первом шаге элемента - также выбираем некоторый опорный ключ и перебрасываем соответствующие большие и меньшие чем он элементы.

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

Выбор опорного элемента

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

Варианты выбора опорного элемента.

• Частичная упорядоченность элементов.
• Наиболее хаотичное расположение элементов.
• Самые распространенные варианты:

• выбор середины отрезка

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

• выбор первого элемента последовательности .

Алгоритм выбора опорного элемента последовательности

Этот алгоритм был впервые описан К. А. Р. Хоаром в его классической статье «Быстрая сортировка»

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

положение первого обмена

Разделение массива

4

9

7

6

2

3

8

i

j

Исходное положение

4

9

7

6

2

3

8

j

i

4

3

7

6

2

9

8

i

Положение второго обмена

j

4

3

2

6

7

9

8

i

j

Положение третьего обмена

=v) or (i=j-1); b:=a[i]; a[i]:=a[j]; a[j]:=b; until i=j; a[j]:=a[i]; a[i]:= a[r]; a[r]:=b; part:=i; end; QuickSort(1,n); writeln; for k:=1 to n do write(a[k]:3); readln; end. " width="640"

Пример: Сформировать массив из 10 элементов. Значения задать ГСЧ. Отсортировать массив методом «быстрой сортировки».

procedure QuickSort(l, t: integer);

var i: integer;

begin

if l

begin

i:=part(l, t);

QuickSort(l,i-1);

QuickSort(i+1,t);

end;

end;

begin

clrscr;

randomize;

for k:=1 to 10 do

begin

a[k]:=random(100);

write(a[k]:3);

end;

program Quitsort;

uses

crt;

Const

N=10;

Type

Mas=array[1..n] of integer;

var

a: mas;

k: integer;

function Part(l, r: integer):integer;

var

v, i, j, b: integer;

begin

V:=a[r];

I:=l-1;

j:=r;

repeat

repeat

dec(j)

until (a[j]

repeat

inc(i)

until (a[i]=v) or (i=j-1);

b:=a[i];

a[i]:=a[j];

a[j]:=b;

until i=j;

a[j]:=a[i];

a[i]:= a[r];

a[r]:=b;

part:=i;

end;

QuickSort(1,n);

writeln;

for k:=1 to n do

write(a[k]:3);

readln;

end.

=v) or (i=j-1); b:=a[i]; a[i]:=a[j]; a[j]:=b; until i=j; a[j]:=a[i]; a[i]:= a[r]; a[r]:=b; part:=i; end; procedure QuickSort(l, t: integer); var i: integer; begin if l begin i:=part(l, t); QuickSort(l,i-1); QuickSort(i+1,t); end; end; begin clrscr; randomize; for k:=1 to 10 do begin a[k]:=random(100); write(a[k]:3); end; QuickSort(1,n); writeln; for k:=1 to n do write(a[k]:3); readln; end.   " width="640"

Пример: Сформировать массив из 10 элементов. Значения задать ГСЧ. Отсортировать массив методом «быстрой сортировки».

program Quitsort;

uses

crt;

Const

N=10;

Type

Mas=array[1..n] of integer;

var

a: mas;

k: integer;

 

function Part(l, r: integer):integer;

var

v, i, j, b: integer;

begin

V:=a[r];

I:=l-1;

j:=r;

repeat

repeat

dec(j)

until (a[j]

repeat

inc(i)

until (a[i]=v) or (i=j-1);

b:=a[i];

a[i]:=a[j];

a[j]:=b;

until i=j;

a[j]:=a[i];

a[i]:= a[r];

a[r]:=b;

part:=i;

end;

procedure QuickSort(l, t: integer);

var i: integer;

begin

if l

begin

i:=part(l, t);

QuickSort(l,i-1);

QuickSort(i+1,t);

end;

end;

begin

clrscr;

randomize;

for k:=1 to 10 do

begin a[k]:=random(100);

write(a[k]:3);

end;

QuickSort(1,n);

writeln;

for k:=1 to n do

write(a[k]:3);

readln;

end.

 

Результат работы программы

60,79, 82, 58, 39, 9, 54, 92, 44, 32

60,79, 82, 58, 39, 9, 54, 92, 44, 32

9,79, 82, 58, 39, 60, 54, 92, 44, 32

9,79, 82, 58, 39, 60, 54, 92, 44, 32

9, 32, 82, 58, 39, 60, 54, 92, 44, 79

9, 32, 44, 58, 39, 60, 54, 92, 82, 79

9, 32, 44, 58, 39, 54, 60, 92, 82, 79

9, 32, 44, 58, 39, 92, 60, 54, 82, 79

9, 32, 44, 58, 39, 54, 60, 79, 82, 92

9, 32, 44, 58, 54, 39, 60, 79, 82, 92

9, 32, 44, 58, 60, 39, 54, 79, 82, 92

9, 32, 44, 58, 54, 39, 60, 79, 82, 92

9, 32, 44, 58, 54, 39, 60, 79, 82, 92

9, 32, 44, 58, 54, 39, 60, 79, 82, 92

9, 32, 39, 58, 54, 44, 60, 79, 82, 92

9, 32, 39, 58, 54, 44, 60, 79, 82, 92

9, 32, 39, 44, 54, 58, 60, 79, 82, 92

9, 32, 39, 44, 58, 54, 60, 79, 82, 92

9, 32, 39, 44, 54, 58, 60, 79, 82, 92

9, 32, 39, 44, 54, 58, 60, 79, 92, 82

9, 32, 39, 44, 54, 58, 60, 79, 82, 92

Заключение

Метод быстрой сортировки позволяет существенно сократить количество операций .

Например: Все предыдущие методы требовали N 2 операций , где N – количество элементов.

Метод быстрой сортировки требует в среднем N*Log 2 N операций .

В случае N=100, выигрыш составляет порядка 100 раз .