Лабораторная работа: Алгоритми сортування

int *X, N;

clock_t start, end;

clrscr ();

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

N=0;

while (! feof (f))

{

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

N++;

}

fclose (f);

start= clock ();

MergeSort (X,0,N-1);

end= clock ();

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

rez=fopen ("rezult. txt","wt");

for (int i=0; i<N; i++)

fprintf (rez,"%d\n",* (X+i));

fclose (rez);

getch ();

}Результат роботи сортування злиттям

Довжина послідовності		Випадкові						Зростає	Спадає
		312	17	927	85	10009	середнє
10	Пересилання	78	78	78	78	78	78	78	78
Порівняння	22	22	22	22	22	22	22	22
50	Пересилання	568	568	568	568	568	568	568	568
Порівняння	257	257	257	257	257	257	257	257
200	Пересилання	3106	3106	3106	3106	3106	3106	3106	3106
Порівняння	818	818	818	818	818	818	818	818
1000	Пересилання	19974	19974	19974	19974	19974	19974	19974	19974
Порівняння	5049	5049	5049	5049	5049	5049	5049	5049
5000	Пересилання	123644	123644	123644	123644	123644	123644	123644	123644
Порівняння	33965	33965	33965	33965	33965	33965	33965	33965
10000	Пересилання	267262	267262	267262	267262	267262	267262	267262	267262
Порівняння	74335	74335	74335	74335	74335	74335	74335	74335

Кількість порівняннь:

Кількість пересилань:

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

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

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

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

Код сортування злиттям: