Быстрая сортировка с ограничением рекурсии

Обзор алгоритмов

Const

nmax = 5000;

Type

tKey = integer;

tData = integer;

tItem = record

Key: tKey;

Data: tData;

end;

tArray=array[1..nmax] of tItem;

Сортировка простым выбором

procedure SelectSort(var a: tArray; n: integer);

Var

i, j, jmin: integer;

buf: tItem;

Begin

for i:= 1 to n-1 do begin

jmin:= i;

for j:= 1 to i-1 do

if a[j].key > a[jmin].key then

jmin:= j;

buf:= a[i];

a[i]:= a[jmin];

a[jmin]:= buf;

end;

end.

 

Сортировка методом Д.Шелла

 

procedure ShellSort(var a: tArray; n: integer);

Var

i, j, h: integer;

x: tItem;

Begin

h:=13;

while h<n do

h:=3*h + 1;

h:=(h - 1) div 3;

Repeat

h:=(h - 1) div 3;

for i:=h + 1 to n do begin

x:=a[i];

j:=i - h;

while (j > 0) and (x.key < a[j].key) do begin

a[j + h]:=a[j];

j:=j - h;

end;

a[j + h]:=x;

end;

until h <= 1;

end;

 

 

Быстрая сортировка с ограничением рекурсии

 

procedure QuickSort(var a: tArray; n: integer);

procedure Sort(L, R: integer);

Var

i, j: integer;

x, y: tItem;

Begin

while L < R do begin

i:=L; j:=R;

x:=a[(L + R) div 2];

Repeat

while x.key > a[i].key do i:=i + 1;

while a[j].key > x.key do j:=j - 1;

if i <= j then begin

y:=a[i];

a[i]:=a[j];

a[j]:=y;

i:=i + 1; j:=j - 1;

end;

until i > j;

if i – L < R - j then begin

Sort(L, j);

l:=i;

End

Else begin

Sort(i, R);

R:=j;

end;

end;

end;

Begin

Sort(1, n);

end;

 

 

Случайный массив

Кол-во элементов	Сортировка простым выбором	Сортировка методом Шелла	Быстрая сортировка с огрн. рек.
Время	Число сравнений ключа	Число пересылок	Время, с	Число сравнений ключа	Число пересылок	Время, с	Число сравнений ключа	Число пересылок
	1601,836757			113,4477251			72,4017339
	6402,887609			329,4280674			226,6895285
	14361,43253			531,1959487			409,7542766
	25499,92922			785,9783052			534,9147375
	39851,71764			1045,06517			720,8894591
	57324,3712			1314,571237			889,6958959
	77883,43558			1579,657417			1070,716681
	101667,0398			1850,444684			1233,883258
	128585,2259			2130,315735			1421,656056
	158523,8082			2364,401484			1601,547939

 

Отсортированный массив

Кол-во элементов	Сортировка простым выбором	Сортировка методом Шелла	Быстрая сортировка с огрн. рек.
Время	Число сравнений ключа	Число пересылок	Время, с	Число сравнений ключа	Число пересылок	Время, с	Число сравнений ключа	Число пересылок
	1601,39662			19,0812573			14,8805805
	6388,966313			69,9939788			74,3388895
	14356,22485			150,6567637			149,1735951
	25544,21216			210,476764			198,9575831
	39835,13891			280,2481636			276,0115434
	57367,18554			347,0238535			357,8946275
	78021,87746			463,4552023			415,9816192
	101943,1232			536,5044669			475,8422242
	128935,1281			581,8522369			522,3087196
	159144,7316			658,2673603			608,4132491

Обратно отсортированный массив

Кол-во элементов	Сортировка простым выбором	Сортировка методом Шелла	Быстрая сортировка с огрн. рек.
Время	Число сравнений ключа	Число пересылок	Время, с	Число сравнений ключа	Число пересылок	Время, с	Число сравнений ключа	Число пересылок
	1587,29439			61,095304			21,1533577
	6323,765326			189,7683288			84,3938507
	14225,0402			311,5236291			170,7748294
	25295,59026			408,3120362			226,2148742
	39505,04711			550,1877857			318,2928401
	56842,79165			700,0719592			408,6996313
	77417,90677			796,435305			471,1712062
	101143,9112			953,2062336			537,6662122
	127890,5549			1082,117967			591,3859857
	158054,8388			1210,459579			691,4279534

 

Число сравнений ключа

Число сравнений ключа

Сортировка Шелла и Быстрая сортировка с ограниченной рекурсией

Сортировка простым выбором

 

Сортировка Шелла и Быстрая сортировка с ограниченной рекурсией

Число пересылок

 

 

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

Сортировка методом Шелла: используется сортировка вставками, применяя принцип уменьшения расстояния между сравниваемыми элементами. Сначала сортируются все элементы, которые смещены друг от друга на три позиции. Затем сортируются все элементы, которые смещены на две позиции. И, наконец, упорядочиваются все соседние элементы.

 

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

На языке Java

protected static void Sort(tItem a[], int L, int R)

{

tItem x;

tItem y;

int i;

int j;

while (L < R)

{

x = a[(L + R) / 2];

i = L; j = R;

do

{

while (a[i].Key < x.key) { i++; };

w hile (x.key < a[j].Key) { j--; };

if (i <= j)

{

y = a[i];

a[i] = a[j];

a[j] = y;

i++;

j--;

}

} while (i <= j);

 

if (j - L < R - i)

{

Sort(a, L, j);

L = i;

}

Else

{

Sort(a, i, R);

R = j;

}

}

}

static void QuickSort(tItem a[], int n)

{

Sort(a, 1, n);

}

 

 

Сортировка простым выбором

Число сравнений ключа:

Число пересылок:

;

 

Параметрах алгоритма

Последовательность предложенная Кнутом: все значения k_k = 3*k_k + 1

Последовательность предложенная Хиббардом: все значения ; такая последовательность шагов приводит к алгоритму сложностью O(N^{3 / 2});

Последовательность предложенная Седжвиком: , если i четное и , если i нечетное. При использовании таких приращений средняя сложность алгоритма составляет: O(n7 / 6), а в худшем случае порядка O(n^{4 / 3}).

Число сравнений ключа

Кол-во элементов:	Кнут	Хиббард	Седжвик
Случайный массив	Отсортированный массив	Обратно отсортированный массив	Случайный массив	Отсортированный массив	Обратно отсортированный массив	Случайный массив	Отсортированный массив	Обратно отсортированный массив

Время

Кол-во элементов:	Кнут	Хиббард	Седжвик
Случайный массив	Отсортированный массив	Обратно отсортированный массив	Случайный массив	Отсортированный массив	Обратно отсортированный массив	Случайный массив	Отсортированный массив	Обратно отсортированный массив
	1,135	0,181	0,648	1,237	0,391	0,762	1,586	0,075	0,954
	3,291	0,747	1,888	3,619	1,325	2,065	4,028	0,803	2,557
	5,426	1,507	3,134	5,824	2,398	3,581	6,384	1,462	3,802
	7,795	2,202	3,955	8,324	3,365	4,846	9,029	2,116	5,192
	10,387	2,808	5,516	11,093	4,692	5,97	11,725	3,091	6,808
	12,887	3,471	7,044	13,913	5,414	8,039	14,641	3,845	8,607
	15,838	4,664	7,257	16,51	6,541	9,159	17,237	4,605	10,314
	18,513	5,394	9,56	19,652	7,561	10,778	20,361	5,42	12,572
	21,442	5,839	10,843	22,913	9,196	11,744	23,264	6,293	13,089
	24,214	6,576	11,095	25,846	10,388	13,684	26,407	7,03

Число пересылок

Кол-во элементов:	Кнут	Хиббард	Седжвик
Случайный массив	Отсортированный массив	Обратно отсортированный массив	Случайный массив	Отсортированный массив	Обратно отсортированный массив	Случайный массив	Отсортированный массив	Обратно отсоритрованный массив

Число сравнений ключа

Время

Число пересылок

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

 

 

Обзор алгоритмов

Const

nmax = 5000;

Type

tKey = integer;

tData = integer;

tItem = record

Key: tKey;

Data: tData;

end;

tArray=array[1..nmax] of tItem;

Сортировка простым выбором

procedure SelectSort(var a: tArray; n: integer);

Var

i, j, jmin: integer;

buf: tItem;

Begin

for i:= 1 to n-1 do begin

jmin:= i;

for j:= 1 to i-1 do

if a[j].key > a[jmin].key then

jmin:= j;

buf:= a[i];

a[i]:= a[jmin];

a[jmin]:= buf;

end;

end.

 

Сортировка методом Д.Шелла

 

procedure ShellSort(var a: tArray; n: integer);

Var

i, j, h: integer;

x: tItem;

Begin

h:=13;

while h<n do

h:=3*h + 1;

h:=(h - 1) div 3;

Repeat

h:=(h - 1) div 3;

for i:=h + 1 to n do begin

x:=a[i];

j:=i - h;

while (j > 0) and (x.key < a[j].key) do begin

a[j + h]:=a[j];

j:=j - h;

end;

a[j + h]:=x;

end;

until h <= 1;

end;

 

 

Быстрая сортировка с ограничением рекурсии

 

procedure QuickSort(var a: tArray; n: integer);

procedure Sort(L, R: integer);

Var

i, j: integer;

x, y: tItem;

Begin

while L < R do begin

i:=L; j:=R;

x:=a[(L + R) div 2];

Repeat

while x.key > a[i].key do i:=i + 1;

while a[j].key > x.key do j:=j - 1;

if i <= j then begin

y:=a[i];

a[i]:=a[j];

a[j]:=y;

i:=i + 1; j:=j - 1;

end;

until i > j;

if i – L < R - j then begin

Sort(L, j);

l:=i;

End

Else begin

Sort(i, R);

R:=j;

end;

end;

end;

Begin

Sort(1, n);

end;

 

 

Случайный массив

Кол-во элементов	Сортировка простым выбором	Сортировка методом Шелла	Быстрая сортировка с огрн. рек.
Время	Число сравнений ключа	Число пересылок	Время, с	Число сравнений ключа	Число пересылок	Время, с	Число сравнений ключа	Число пересылок
	1601,836757			113,4477251			72,4017339
	6402,887609			329,4280674			226,6895285
	14361,43253			531,1959487			409,7542766
	25499,92922			785,9783052			534,9147375
	39851,71764			1045,06517			720,8894591
	57324,3712			1314,571237			889,6958959
	77883,43558			1579,657417			1070,716681
	101667,0398			1850,444684			1233,883258
	128585,2259			2130,315735			1421,656056
	158523,8082			2364,401484			1601,547939

 

Отсортированный массив

Кол-во элементов	Сортировка простым выбором	Сортировка методом Шелла	Быстрая сортировка с огрн. рек.
Время	Число сравнений ключа	Число пересылок	Время, с	Число сравнений ключа	Число пересылок	Время, с	Число сравнений ключа	Число пересылок
	1601,39662			19,0812573			14,8805805
	6388,966313			69,9939788			74,3388895
	14356,22485			150,6567637			149,1735951
	25544,21216			210,476764			198,9575831
	39835,13891			280,2481636			276,0115434
	57367,18554			347,0238535			357,8946275
	78021,87746			463,4552023			415,9816192
	101943,1232			536,5044669			475,8422242
	128935,1281			581,8522369			522,3087196
	159144,7316			658,2673603			608,4132491