Характеристики внутренних методов сортировки. Дополнительные факторы, учитываемые при сортировке.

1. Линейная – если элементы для сравнения выбираются последовательно, иначе если существуют какие то правила для выбора элементов, то не линейная сортировка.

2. Простые, комбинированные. Если на протяжение всего процесса сортировки используется один и тот же метод, то это простоя сортировка. Если происходит изменение метода при каких либо условиях, то это комбинированная сортировка.

3. Сравнительные, распределительные. В сравнительных сортировках ключ рассматривается как единое целое, в распределительных ключ рассматривается по составляющим.

Основной критерий, по которому происходит выбор сортировки: Количество сравнений, кол-во перемещений.

Дополнительные критерии:

§ Характеристики выбираемых данных:

1. Размер последовательности ( внутренний или внешний, сколько памяти потребуется для реализации сортировки).

2. Характеристики ключа (Размер ключа, ключ является единым или составным, отдельно вводится является ли ключ машинным словом, ключ так же может состоять из разных частей машинных слов, в какой системе кодировки находятся данные)

3. Распределение ключей (есть какое то частичное упорядочивание; имеется ли дублирование значений ключей)

4. Какова длина и изменчивость значений в целом, обмен всегда производится только записями фиксированной длины

5. Возможны сортировки обособленными ключами (Создается дополнительный массив с двумя составляющими, Ключ и Адрес элемента подлежащего сортировки)

§ Программные связи, они определяют:

1. Источник данных, процесс сортировки изолирован, он производится с каким то условием.

2. Требуются ли физические перемещения данных

§ Характеристики самой машины:

1. Кол-во регистров

2. Логика операций сравнений

3. Временные характеристики операции сравнения

4. Какие процессы сравнения реализуются на данной машине

5. Объем ОП и внешней памяти, так же вид внешней памяти

6. Возможности маскировки данных и т.д.

Реализация алгоритма простых вставок. Оценка сложности алгоритма.

· A1 ….ак – уже отсортированный Ак+1….аn – не отсортирован

Наитии место Ак+1 в не отсортированной части

· Сравниваем последовательно значение Ак+ 1 с отсортированной частью , начиная с Ак , Ак-1 итд

· Отрезок Аi +1….ак сдвигается на массиве вправо на 1 позицию. Элемент ак+1 становится на старое место аi+1

ПР: 1 7 -3 18 0 -3 1 7 18 0

1 7 -3 18 0 -3 0 1 7 18

procedureStraightlnsertion;

var I,j: Index; x: Item;

Begin

for i:= 2 ton do

beginx := A[i]; {передвигаемый в левую часть элемент}

А[0] := х; {фиктивный элемент массива -"барьер", установ­ленный на тот случай, когда А[ I ] должен перемес­титься на первое место}

j:= i- l; {правый край левой части }

whilex. key < A[j].key do

Begin

A[ j + 1] := A [ j ]; j := j - 1 {продвижение "дырки" в левой части массива справа налево до той позиции, в которую должен быть включен элемент А[ i ].}

end;

A [ j + 1] := х {включение А[ i ] в "дырку" в левой части'}

end;

end;

Реализация алгоритма простого выбора. Оценка сложности алгоритма.

· А1…An – выбираем минимальный элемент

· Минимальный элем становится на 1-е место , а 1 элемент становится на место минимального

· И а2….аn итд

ПР: 1 7 -3 18 0

-3 7 1 18 0

-3 0 1 18 7

-3 0 1 18 7

-3 0 1 7 18

const n=10;

type Tarray = array [1..n] of integer;

procedure vibor (var a:Tarray);

var i, j: integer; min, buf: integer;

begin

for j:=1 to n do begin

min:=a[1];

for i:=1 to n do begin

buf:=1;

min:=a[i];

end; end;

if (a[i]>min)

then begin

a[buf]:=a[j];

a[j]:=min;

end; end; end;

Реализация алгоритма простого обмена. Оценка сложности алгоритма.

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

Сортировка пузырьком:

procedure bubble (var a: Tarray);

var i, buf, j: integer;

begin

for i:=1 to n-1 do

for i:=n downto i-1 do

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

then begin

buf:=a[i];

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

a[i-1]:=buf;

end; end;

Реализация алгоритма простого подсчета. Оценка сложности алгоритма.

· Требует дополнительной памяти ( для счетчиков)

· А1….аn – заводится такой же массив с такой же размерностью , и целочисленными элементами В1….Вn ( это массив счетчика ). Каждый из элементов соответствует элементу исходного массива (В1 – А1) Много времени тратится на перемещение элементов. Особенно если массив большой размерности.

· Каждый эл-т исходного массива сравнивается со всеми последующими. Пусть исходный элемент Аi, Ак – последний элемент – если Аi<Ак то счетчик элемента Ак увиличивается на 1, если А i>Ак - то увиличиваем счетчик Аi на 1

for i:=1 to n do c[a[i]]:=c[a[i]]+1; p:=0; i:=0; repeat inc(i); if c[i]>0 then for j:=1 to c[i] do begin inc(p); a[p]:=i; end; until p=n;

Procedure BinaryInsert(var a:Tarray);

Var I,l,r,k:integer;

Begin

For i:=2 to N do begin

X=:a[r]; r:=i-1;l:=1;

While (l<r) do begin

K:=(l+r) div2;

If x>a[k] then l:=k+1

Else r:=k-1;

End;

If (i-1)mod2=0 then r:=r-1;

For k:=i-1 downto (r+1) do a[k+1]:=a[k];

A[r+1}:=x;

End;

End;

Реализация алгоритма парного обмена. Оценка сложности алгоритма.

· Сначала производится сравнение элементов которые стоят на нечетных позициях с элем- ми которые стоят на следующих четных

· Если условие нарушается , то производим обмен элементами

· После этого сначала массива производим сравнение элементов которые стоят на четных позициях со следующими не четными ,если условие нарушается то обмен

При каждой из перестановок производится подсчет сколько раз был произведен обмен на каждой из перестановок если 0 то сортировка прекращается.

ПР:

3 3 3 3 3 3 3

11 11 4 4 4 4 4

6 4 11 5 5 5 5

4 6 5 11 6 6 6

5 5 6 6 11 9 9

9 9 9 9 9 11 11

Сортировка парным обменом:

procedure vibor (var a:Tarray);

var i, x: integer; f: boolean;

begin

f:=false;

while (f=false) do begin

f:=true;

for i:=1 to n do

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

then begin

x:=a[i];

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

a[i+1]:=x;

f:=false;

end; end; end;

Реализация алгоритма центрированных вставок. Оценка сложности алгоритма.

· Заводится дополнит массив куда записывается результат , на место основного массива не пишется

· В дополнительном массиве : первый элемент пишется на центральное место в результирующем массиве. Все следующие элементы сравниваются с центральным элементом : если меньше 1-го элемента , то его место ищут в левой части если больше то в правой

· Дальше обычным методом простых вставок

ПР:

1. 3 1

2. 11 2 3

3. 6 3 3 4

4. 4 4. 3 4 5

5. 5 5. 11 6 4 5 6

6. 9 6. 11 6 6 9

7. 7 7. 11 11 11

Procedure CentredInsert(var a:TArray);

Var I,L,r,x,j:integer;

B:TArray;

Begin

L:=Ndiv2; r:=L;

B[L]:=a[1];

For i:=2 to N do begin

If x<b[i] then

Begin

J:=c-1;

While (j<l) and (b[j]>x) do j:=j-1;

If l>1 then begin

For

………………..

Else begin

J:=l+1

While (j<r) and (b[j]<x) do

J:=j+1;

If r<N then begin

For k:=r downto j do b[k+1]:=b[k];

B[j]:=x;

R:=r+1;

End

Else begin

For k:=l to j-1 do b[k-1]:=b[k];

B[j-1]:=x;

L:=l+1;

End; end; end;

For i:=1 to n do a[i]:=b[i];

End;

Реализация алгоритма квадратичного выбора. Оценка сложности алгоритма.

Исходный массив разбивается на корень из N , отводится дополнит массив для хранения результатов. Еще дополнит массив с количеством элементов корень из N . В каждой из частей производится выборка элементов обычным методом. Результат помещается в дополнит массив из корень из N элементов , дальше выбирается выборка из дополнит массива и элемент переносится в результирующий массив.

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

procedure Quad(var t: data; var cmpcnt, xchcnt: integer);

var sel: array [1..sqrtn, 1..sqrtn] of integer;

max, imax: array [1..sqrtn] of integer;

i, j, l, m, im, jm: integer;

res: data;

begin

for i:=1 to sqrtn do

for j:=1 to sqrtn do sel[i, j] := t[(i-1) * sqrtn + (j-1)].k;

cmpcnt := 0;

xchcnt := 0;

for i:=1 to sqrtn do

begin

max[i] := sel[i, 1];

imax[i] := 1;

for j := 2 to sqrtn do

begin

inc(cmpcnt);

if sel[i,j] > max[i] then

begin

max[i] := sel[i, j];

imax[i] := j;

end;

end;

end;

for l := N downto 1 do

begin

i := 1;

while max[i] = 0 do inc(i);

m := max[i];

im := i;

jm := imax[i];

for j := i+1 to sqrtn do if max[j] > 0 then

begin

inc(cmpcnt);

if max[j] > m then

begin

m := max[j];

im := j;

jm := imax[j];

end;

end;

res[l] := t[(im-1)*sqrtn + (jm-1)];

inc(xchcnt);

sel[im, jm] := 0;

jm := 1;

while (sel[im, jm] = 0) and (jm <= sqrtn) do inc(jm);

if jm > sqrtn then

begin

max[im] := 0;

imax[im] := 0;

end

else

begin

max[im] := sel[im, jm];

imax[im] := jm;

for j:=jm + 1 to sqrtn do if sel[im, j] > 0 then

begin

inc(cmpcnt);

if sel[im, j] > max[im] then

begin

max[im] := sel[im, j];

imax[im] := j;

end;

end;

end;

end;

t := res;

end;

Реализация алгоритма поразрядной сортировки. Оценка сложности алгоритма.

Ключ рассматривается из составляющих ключ строится в некотором алфавите. Исходя из количества символов алфавита определяется количество бункеров которое соответствует каждому символу алфавита. Сначала производится распределение исходных значений по бункерам исходя по младшему разряду ключа , потом последовательно собираются в исходный массив. Далее тоже самое по следующему разряду ключа до самого старшего

// инициализация дополнительных списков - "карманов"

pockets = array[range]

for i = 0 to range - 1

pockets[i] = newArray

// Основной цикл

for step = 0 to width - 1

// распределение

for i = 0 to (sortedArr.length - 1)

// Получаем значение step-го разряда текущего элемента(ключа)

// ("/" - целочисленное деление)

currDigit = (sortedArr[i] % range^(step + 1)) / range^step

pockets[currDigit].add(sortedArr[i]);

// сборка

k = 0 // индекс элементов новой последовательности

for i = 0 to range - 1

for ii = 0 to (pockets[i].length - 1)

sortedArr[k++] = pockets[i][ii]

// Очищение карманов

if step < width - 1

for i = 0 to range - 1

pockets[i] = newArray