Jeste li se ikad zapitali kako se proizvodi na Amazonu ili bilo kojoj drugoj online trgovini sortiraju kada promijenite filtere poput sortiranja po cijeni od najniže prema najvišoj, od najviše prema najnižoj ili abecedno? Algoritmi za sortiranje igraju vitalnu ulogu za takve web stranice na kojima imate ogromnu količinu proizvoda na popisu i morate olakšati interakciju kupcima.
Algoritam za sortiranje se koristi za preuređivanje datog niza ili popisa elemenata prema operatoru usporedbe na elementu. Operator usporedbe se koristi za odlučivanje o novom redoslijedu elemenata u odgovarajućoj strukturi podataka. Uglavnom se koristi pet osnovnih algoritama i pomoću ovih osnovnih algoritama možete izvesti neke kompleksnije algoritme. Svaki od ovih algoritama ima neke prednosti i nedostatke i može se učinkovito odabrati ovisno o količini podataka kojima se treba rukovati.
-
Insertion Sort
Sortiranje umetanjem (Insertion sort) je jednostavan algoritam za sortiranje koji djeluje slično načinu na koji sortirate igraće karte u rukama. Niz je gotovo podijeljen na razvrstani i nerazvrstani dio. Vrijednosti iz nerazvrstanog dijela se biraju i po stavljaju na ispravan položaj u razvrstanom dijelu. Sortiranje umetanjem je brzo i najprikladnije bilo kada je količina elemenata mala ili kada su podaci gotovo do kraja sortirani.
Algoritam:
https://gist.github.com/adwiteeya3/79c240eb0701381d30368fffd9580129#file-insertion-sort-c
void InsertionSort(int arr[], int n){
int i, key, j;
for(i = 1; i < n; i++){
key = arr[i];
j = i – 1;
while(j >= 0 && arr[j] > key){
arr[j + 1] = arr[j];
j = j – 1;
}
arr[j + 1] = key;
}
}
Insertion Sort
-
Selection Sort
Selection sort algoritam sortira niz ponavljajući pronalaženje minimalnog elementa (uzimajući u obzir uzlazni poredak) iz nerazvrstanog dijela i stavljajući ga na početak. Algoritam održava dva podniza u danom nizu:
- Podniz koji je već sortiran
- Preostali podskup koji još nije sortiran
U svakoj iteraciji/prolazu se bira minimalni element (s obzirom na uzlazni poredak) iz nerazvrstanog podniza i premješta se u razvrstani niz. Selection sort ima svojstvo minimiziranja broja zamjena. Stoga je najbolji izbor kada su troškovi zamjene visoki.
Algoritam:
https://gist.github.com/adwiteeya3/9a8446cbfacfee921ba68a7a593ecf36#file-selection-sort-c
void swap (int *xp, int *yp){
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void SelectionSort (int arr[], int n){
int i, j, min_idx;
for (i = 0; i < n – 1; i++){
min_idx = i;
for (j = i + 1; j < n; j++){
if (arr[j] < arr[min_idx])
min_idx = j;
swap (&arr[min_idx], &arr[i]);
}
}
Selection Sort
-
Bubble Sort
Bubble sort je algoritam sortiranja koji funkcionira ponavljajući zamjenu susjednih elemenata ako su u pogrešnom redoslijedu. Nakon svake iteracije ili prolaska najveći element ide na kraj (u slučaju rastućeg reda) ili najmanji element dolazi na kraj (u slučaju silaznog reda). Prolazak kroz elemente se ponavlja dok se niz ne sortira. Ovaj algoritam nije prikladan za velike skupove podataka jer su njegova prosječna i složenost u najgorem slučaju O(n^2) gdje je n broj elemenata u popisu ili polju.
Algoritam:
https://gist.github.com/adwiteeya3/9ab981f31774ec898c1b59b0c9700f3b#file-bubble-sort-c
void swap (int *xp, int *yp){
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void BubbleSort (int arr[], int n){
int i, j;
bool swapped;
for (i = 0; i < n – 1; i++){
swapped = false;
for(j = 0; j < n – i – 1; j++){
if (arr[j] > arr[j + 1]){
swap (&arr[j], &arr[j + 1]);
swapped = true;
}
}
if (swapped == false)
break;
}
}
Bubble Sort
-
Merge Sort
Za razliku od gornja tri algoritma za sortiranje, ovaj se algoritam temelji na tehnici podijeli pa vladaj. Dijeli ulazni niz na dvije polovice, poziva se na te dvije polovice i nakon toga spaja te dvije polovice u jednu cjelinu. Srce Merge Sort algoritma je „merge()“ funkcija koja se koristi za spajanje dviju polovica. Spajanje je ključni postupak koji pretpostavlja da su dvije polovice sortirane i spaja ih u jednu cjelinu. Merge sort je opcija kada vam je potrebno stabilno i O (n * log(n) ) sortiranje.
„merge“ funkcija
U nastavku možemo pogledati princip rada Merge Sort-a.
Algoritam:
https://gist.github.com/adwiteeya3/a19665cbbecbe1126a54e06c477ce951#file-merge-sort-c
void merge (int arr[], int l, int m, int r){
int i, j, k;
int n1 = m – l + 1;
int n2 = r – m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2){
if (L[i] <= R[j]){
arr[k] = L[i];
i++;
}
else{
arr[k] = R[j];
j++;
}
k++;
}
while(i < n1){
arr[k] = L[i];
i++;
k++;
}
while (j < n2){
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort (int arr[], int l, int r){
if (l < r){
int m = l + (r – 1) / 2;
mergeSort (arr, l , m);
mergeSort (arr, m + 1, r);
merge (arr, l, m, r);
}
}
Merge Sort
-
Quick Sort
Brzo sortiranje (quick sort) je također podijeli i vladaj algoritam. Odabire element kao stožer i pregrađuje zadani niz oko odabranog pivota tako da su svi manji elementi lijevo od pivota, a svi veći elementi desno od pivota. Postoji mnogo različitih verzija Quick Sort algoritma koji biraju pivota na različite načine:
- Uvijek odaberite prvi element kao pivota
- Uvijek odaberite zadnji element kao pivota
- Odaberite slučajni element kao pivota
- Odaberite medijan kao pivota
Ključni proces u brzom sortiranju je „partition()“ metoda. Cilj particije je, dajući niz i element r niza kao stožer, staviti r na njegov ispravan položaj u sortiranom nizu i staviti sve manje elemente (manje od r) ispred r, a sve veće elemente poslije r. Sve to treba učiniti linearno.
Za male količine podataka brzo sortiranje je najbolji algoritam u usporedbi s merge sort-om. Kada vam nije potrebno stabilno sortiranje, a izvedba u prosječnom slučaju je važnija od izvedbe u najgorem, idite na quick sort. Pogledajmo prvo „partition“ metodu i njenu implementaciju.
Algoritam:
https://gist.github.com/adwiteeya3/f1797534506be672b591f465c3366643#file-quick-sort-c
void swap (int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}
int partition (int arr[], int low, int high){
int pivot = arr[high];
int i = (low – 1);
for (int j = low; j <= high – 1; j++){
if (arr[j] < pivot){
i++;
swap (&arr[i], &arr[j]);
}
Swap (&arr[i + 1], &arr[high]);
return (i + 1);
}
void quickSort (int arr[], int low, int high){
if (low < high){
int pi = partition (arr, low, high);
quickSort (arr, low, pi – 1);
quickSort (arr, pi + 1, high);
}
}
Quick Sort
Izvor: medium.com
Piše: A. M.
