Implementacije algoritama sortiranja
Implementacije napisao dr Filip Marić (http://poincare.matf.bg.ac.rs/~filip/)
/* Poredimo i-ti i j-ti element niza a */
int uporedi(int a[], int i, int j) {
br_poredjenja++;
return a[i] > a[j];
}
/* Menjamo i-ti i j-ti element niza a */
void zameni(int a[], int i, int j) {
br_zamena++;
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
/* Selection sort */
void selection_sort_1(int a[], int n) {
int i, j;
for (i = 0; i < n-1; i++)
for (j = i+1; j < n; j++)
if (uporedi(a, i, j))
zameni(a, i, j);
}
void selection_sort_2(int a[], int n) {
int i, j, min;
for (i = 0; i < n - 1; i++) {
min = i;
for (j = i+1; j < n; j++)
if (uporedi(a, min, j))
min = j;
if (i != min)
zameni(a, i, min);
}
}
/* Insertion sort */
void insertion_sort_1(int a[], int n) {
int i, j;
for (i = 1; i < n; i++)
for (j = i; j > 0 && uporedi(a, j-1, j); j--)
zameni(a, j-1, j);
}
/* Broj dodela se moze redukovati tako sto se umesto
zamena koristi dodela privremenoj promenljivoj */
void insertion_sort_2(int a[], int n) {
int i, j;
for (i = 1; i < n; i++) {
int tmp = a[i];
for (j = i; j > 0 && a[j-1] > tmp; j--){
a[j] = a[j-1];
}
a[j] = tmp;
}
}
/* Bubble Sort */
/* Najjednostavnija implementacija - menjamo uzastopne dok god ima promena */
void bubble_sort_1(int a[], int n) {
int bilo_zamena;
do {
int i;
bilo_zamena = 0;
for (i = 0; i < n-1; i++)
if (uporedi(a, i, i+1)) {
zameni(a, i, i+1);
bilo_zamena = 1;
}
} while(bilo_zamena);
}
/* Malo ubrzanje se moze postici ukoliko se primeti da posle svakog
prolaza najveci ispliva na kraj, tako da se svaki naredni prolaz
skracuje za jednu poziciju. */
void bubble_sort_2(int a[], int n) {
int i, j;
for (i = n-1; i > 0; i--)
for (j = 0; j < i; j++)
if (uporedi(a, j, j+1))
zameni(a, j, j+1);
}
/* Kombinujemo prethodnu optimizaciju sa
prvobitnim kriterijumom zaustavljanja. */
void bubble_sort_3(int a[], int n) {
int i, j;
int bilo_zamena = 1;
for(i = n-1; bilo_zamena; i--) {
bilo_zamena = 0;
for (j = 0; j < i; j++) {
if (uporedi(a, j, j+1)) {
zameni(a, j, j+1);
bilo_zamena = 1;
}
}
}
}
/*Shell sort*/
void shell_sort_1(int a[], int n) {
int sirina;
int i, j, k;
for (sirina = n/2; sirina >= 1; sirina /= 2)
for (k = 0; k < sirina; k++)
/* Elementi k-te kolone su:
a[k], a[k+sirina], a[k+2*sirina],...
Sortiramo je koristeci insertion sort...
*/
for (i = k + sirina; i < n; i += sirina)
for (j = i; j > k && uporedi(a, j-sirina, j); j -= sirina)
zameni(a, j-sirina, j);
}
/* Malo pametnija implementacija - ne sortiramo jednu kolonu nakon druge,
vec dopustamo da sortiranje tece paralelno. Nakon sto element neke kolone
pronadje svoje mesto, prelazimo na obradu elementa do njega,
umesto elementa ispod njega. Ovim se ne dobija sustinsko ubrzanje,
ali cini kod malo jednostavnijim. */
void shell_sort_2(int a[], int n) {
int sirina;
int i, j, k;
for (sirina = n/2; sirina >= 1; sirina /= 2)
for (i = sirina; i < n; i++)
for (j = i; j >= sirina && uporedi(a, j-sirina, j); j -= sirina)
zameni(a, j-sirina, j);
}
/* Quick sort */
void quicksort(int a[], int l, int d) {
int s = (l+d) / 2;
int piv = a[s], t, m;
if (l >= d)
return;
/* Pvi korak je razdvojiti niz tako da bude oblika
< < < < piv >= >= >=
Ovo se odvija u nekoliko koraka. */
swap(a, l, s);
/* piv x x x x x x x x x */
/* piv < < < >= >= >= x x */
/* m t */
m = l;
for (t = l+1; t <= d; t++)
if (a[t] < piv)
swap(a, t, ++m);
/* piv < < < < >= >= >= >= */
/* m */
swap(a, l, m);
/* < < < < piv >= >= >= >= */
quicksort(a, l, m-1);
quicksort(a, m+1, d);
}
/* Merge sort */
void mergesort(int a[], int l, int d) {
int s = (l + d)/2;
static int b[100];
int i, j, k;
if (l >= d)
return;
mergesort(a, 0, s);
mergesort(a, s+1, d);
i = l;
j = s+1;
k = 0;
while (i <= s && j <= d) {
if (a[i] < a[j]) {
b[k++] = a[i++];
}
else {
b[k++] = a[j++];
}
}
while(i <= s)
b[k++] = a[i++];
while(j <= d)
b[k++] = a[j++];
for (k = 0, i = l; i<=d; k++, i++)
a[i] = b[k];
}