Каталог Рефератов - Алгоритми сортування - скачать рефераты, бесплатно рефераты

	Информационно-образоательный портал
	Рефераты, курсовые, дипломы, научные работы,



МЕНЮ\|

поиск

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

Лабораторна робота

Вивчення алгоритмів сортування

Мета: Ознайомитися із простими алгоритмами сортування та навчитися їх програмувати. Засвоїти базові умови тестування програм та вимірювання їх ефективності.

Хід роботи

Сортування вставками

Сортування вставками - простий алгоритм сортування на основі порівнянь. На великих масивах є значно менш ефективним за такі алгоритми, як швидке сортування, пірамідальне сортування та сортування злиттям. Однак, має цілу низку переваг:

простота у реалізації

ефективний (за звичай) на маленьких масивах

ефективний при сортуванні масивів, дані в яких вже непогано відсортовані: продуктивність рівна O (n + d), де d - кількість інверсій

на практиці ефективніший за більшість інших квадратичних алгоритмів (O (n2)), як то сортування вибором та сортування бульбашкою: його швидкодія рівна n2/4, і в найкращому випадку є лінійною є стабільним алгоритмом

Код програми сортування вставками:

#include <stdio. h>

#include <conio. h>

#include <stdlib. h>

#include <time. h>

// Insertion-------------------------------------------------------------

void Insertion (int *arr, int n)

{

int i,j,buf;

clock_t start, end;

FILE *rez;

start = clock ();

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

{

buf=* (arr+i);

for (j=i-1; j>=0 && * (arr+j) >buf; j--)

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

* (arr+j+1) =buf;

}

end = clock ();

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

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

for (i=0; i<n; i++)

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

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

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

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

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

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

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

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

Сортування триватиме до тих пір поки довжина відсортованої підпослідовності не стане рівною довжині самої послідовності.

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

#include <stdio. h>

#include <conio. h>

#include <stdlib. h>

#include <time. h>

// Merge-----------------------------------------------------------------

void merge (int *a, int l, int m, int r)

{

int h, i,j,b [10000],k;

h=l;

i=l;

j=m+1;

while ( (h<=m) && (j<=r))

{

if (a [h] <=a [j])

{

b [i] =a [h];

h++;

}

else

{

b [i] =a [j];

j++;

}

i++;

}

if (h>m)

{

for (k=j; k<=r; k++)

{

b [i] =a [k];

i++;

}

else

{

for (k=h; k<=m; k++)

{

b [i] =a [k];

i++;

}

for (k=l; k<=r; k++) {a [k] =b [k]; }

}

void MergeSort (int *a, int l, int r)

{

int m;

if (l<r)

{

m= (l+r) /2;

MergeSort (a,l,m);

MergeSort (a,m+1,r);

merge (a,l,m,r);

}

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

void main ()

{

FILE *f,*rez;

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

Страницы: 1, 2

© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент.