Швидкодія роботи сортування злиттям

Час виконання оцінюється як , що означає, що цей алгоритм можна використовувати для великих і дуже великих масивів. При сортуванні злиттям потрібне виділення додаткової пам’яті пропорційної , на відміну від сортування купою.

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

Швидке сортування (англ. Quick Sort) - алгоритм сортування, добре відомий, як алгоритм розроблений Чарльзом Хоаром, який не потребує додаткової пам'яті і виконує у середньому O (n log (n)) операцій. Однак, у найгіршому випадку робить O (n²) порівнянь. Оскільки алгоритм використовує дуже прості цикли і операції, він працює швидше інших алгоритмів, що мають таку ж асимптотичну оцінку складності.

Ідея алгоритму полягає в переставлянні елементів масиву таким чином, щоб його можна було розділити на дві частини і кожний елемент з першої частини був не більший за будь-який елемент з другої. Впорядкування кожної з частин відбувається рекурсивно. Алгоритм швидкого сортування може бути реалізований як у масиві, так і в двозв’язному списку.

Швидке сортування є алгоритмом на основі порівнянь, і не є стабільним.

Реалізація зовнішньої процедури сортування швидке на мові С++

#include <conio. h>

#include <stdlib. h>

#include <time. h>

 // ----------------------------------------------------------------------

void QuickSort (int *arr, int a, int b)

{

int i=a, j=b, m = rand ()% (b-a) +a;

int x = * (arr+m);

do

{

while (i<=b && * (arr+i) < x) i++;

while (j>=a && * (arr+j) > x) j--;

if (i <= j)

{

if (i < j)

{

int buf=* (arr+i);

* (arr+i) =* (arr+j);

* (arr+j) =buf;

}

i++;

j--;

}

} while (i <= j);

if (i < b) QuickSort (arr, i,b);

if (a < j) QuickSort (arr,a,j);

}

 // ---------------------------------------------------------------------

void main ()

{

FILE *f;

int *X, N;

clock_t start, end;

N=0;

f=fopen ("massiv. txt","rt");

start= clock ();

while (! feof (f))

{

fscanf (f,"%d",X+N);

N++;

}

QuickSort (X,0,N-1);

end= clock ();

printf ("The time was:%f s\n", (end - start) / CLK_TCK);

start= clock ();

fclose (f);

getch ();

}

#include <stdio. h>

Результат роботи швидкого сортування
Довжина послідовності		Випадкові						Зростає	Спадає
		312	17	927	85	7009	середнє
10	Пересилан-ня	31	21	35	30	35	30,4	6	21
	Порівняння	16	20	11	19	13	15,8	23	15
50	Пересилан-ня	258	240	259	240	255	250,4	31	107
	Порівняння	186	249	188	171	178	194,4	214	213
200	Пересилан-ня	1219	1292	1240	1227	1241	1243,8	126	428
	Порівняння	1130	1357	1149	1377	1308	1264,2	1562	1433
1000	Пересилан-ня	8055	7945	8038	7997	8109	8028,8	642	2139
	Порівняння	7697	7652	6906	7161	7030	7289,2	11779	9793
5000	Пересилан-ня	48603	47722	48371	48384	48839	48383,8	3167	10664
	Порівняння	47782	55603	46085	48296	44447	48442,6	69909	62812
7000	Пересилан-ня	104555	103469	103598	103603	104151	103875,2	6333	263688
	Порівняння	97973	106301	106409	106769	106294	104749,2	148007	140384