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

Кол-во элементов	Сортировка простым выбором	Сортировка методом Шелла	Быстрая сортировка с огрн. рек.
Время	Число сравнений ключа	Число пересылок	Время, с	Число сравнений ключа	Число пересылок	Время, с	Число сравнений ключа	Число пересылок
	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

void SelectSort(tItem a[], int n)

{ int i, j, jmin;

tItem buf;

for (i = 1; i > n-1; i--)

{ jmin = i;

for (j = 1; j < i-1; j++)

if (a[j].key <(a[jmin].key))

jmin = j;

buf = a[i];

a[i] = a[jmin];

a[jmin] = buf;

}

}

 

Сортировка методом Шелла на языке Си#

 

 

void ShellSort(tItem[] a, int n){

int h=13;

int i, j;

tItem x;

while (h < n){

h = 3*h + 1;

}

h = (h - 1) % 3;

do {

h = (h - 1) % 3;

for (i = h+1; i <= n; i++){

buf = a[i];

j = i-h;

while ((j > 0) && (a[j].key < x.key)

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

j--;

}

}

a[j + h] = buf;

} while (h <= 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);

}

 

 

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

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

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

;

 

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

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

C = n + (2*n/2) + (4*n/4) + … + (n*n/n) = n * k = n * log(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

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

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

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

Время

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

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