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

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

fclose (rez);

}

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

void main ()

{

FILE *f;

int *X, N;

clock_t start, end;

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

N=0;

while (! feof (f))

{

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

N++;

}

fclose (f);

clrscr ();

Insertion (X,N);

getch ();

}

Результат роботи сортування вставками
Довжина послідовності		Випадкові						Зростає	Спадає
		312	17	927	85	10009	середнє
Час	0	0	0	0	0	0	0	0
10	Пересилан-ня	38	37	41	35	35	37,2	18	63
Порівняння	29	28	32	26	26	28,2	9	54
Час	0	0	0	0	0	0	0	0
50	Пересилан-ня	816	647	691	679	668	700,2	98	1323
Порівняння	767	598	642	630	619	651,2	49	1274
Час	0	0	0	0	0	0	0	0
200	Пересилан-ня	10003	11251	9802	10387	10455	10379,6	398	20298
Порівняння	9804	11052	9603	10188	10256	10180,6	199	20099
Час	0	0	0	0	0	0	0	0
1000	Пересилан-ня	255877	250330	249604	249928	252295	251606,8	1998	501498
Порівняння	254879	249331	248605	248929	251296	250608	999	500499
Час	0,054	0,055	0,054	0,054	0,55	0,054	0	0,1
5000	Пересилан-ня	6302053	6183921	6229604	6391053	6282323	6277791	9998	12507498
Порівняння	6297054	6178922	6224605	6386054	6277324	6272792	4999	12502499
Час	0,21	0,21	0,21	0,21	0,22	0,21	0	0,44
10000	Пересилан-ня	25166644	24940616	24897941	24822544	24963312	24958211	19998	50014998
Порівняння	25156645	24930617	24887942	24812545	24953313	24948212	9999	50004999

Час виконання:

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

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

Сортування злиттям

Сортування злиттям - алгоритм сортування, в основі якого лежить принцип Розділяй та володарюй. В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву. Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє, поки одна з колон не вичерпається - тоді решта іншої колони додається до нової.

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