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

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

Хід роботи

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

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

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

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

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

на практиці ефективніший за більшість інших квадратичних алгоритмів (O (n² )), як то сортування вибором та сортування бульбашкою: його швидкодія рівна n² /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");

--> ЧИТАТЬ ПОЛНОСТЬЮ <--