1. Selection Sort
Algoritam selection sort se ukratko može opisati na sledeći način: ako niz ima više od jednog elementa, zameni početni element sa najmanjim elementom niza i zatim analogno sortiraj ostatak niza (elemente iza početnog). U svakoj iteraciji se na svoju poziciju dovodi sledeći po veličini element niza, tj. u i-toj iteraciji se i-ti po veličini element dovodi na poziciju i.
Ovo se može realizovati tako što se pronađe pozicija m najmanjeg elementa od pozicije i do kraja niza i zatim se razmene element na poziciji i i element na poziciji m. Algoritam se zaustavlja kada se pretposlednji po veličini element dovede na pretposlednju poziciju u nizu.
Primer: Niz [64, 25, 12, 22, 11]
1. Tražimo min u [64...11] -> to je 11. Razmena 64 i 11. Niz: [11, 25, 12, 22, 64]
2. Tražimo min u [25...64] -> to je 12. Razmena 25 i 12. Niz: [11, 12, 25, 22, 64]
3. Tražimo min u [25...64] -> to je 22. Razmena 25 i 22. Niz: [11, 12, 22, 25, 64]
2. Bubble Sort
Algoritam Bubble sort u svakom prolazu kroz niz poredi uzastopne elemente i razmenjuje im mesta ukoliko su u pogrešnom poretku. Prolasci kroz niz ponavljaju se sve dok se ne napravi prolaz u kojem nije bilo razmena, što znači da je niz sortiran.
Nakon k-te iteracije spoljašnje petlje, k-ti najveći element je na svojoj finalnoj, ispravnoj poziciji. Bubble sort je na osnovu ovog svojstva i dobio ime (jer veliki elementi kao mehurići "isplivavaju" ka kraju niza). Smatra se veoma lošim algoritmom i ne treba ga koristiti u praksi.
Prikaži rad algoritma na primeru sortiranja niza (6 1 4 3 9):
Prvi prolaz:
- ( .6 1 4 3 9 ) → ( 1 6 4 3 9 ), razmena jer je 6 > 1
- ( 1 .6 4 3 9 ) → ( 1 4 6 3 9 ), razmena jer je 6 > 4
- ( 1 4 .6 3 9 ) → ( 1 4 3 6 9 ), razmena jer je 6 > 3
- ( 1 4 3 .6 9 ) → ( 1 4 3 6 9 )
Drugi prolaz:
- ( 1 4 3 6 9 ) → ( 1 4 3 6 9 )
- ( 1 4 3 6 9 ) → ( 1 3 4 6 9 ), razmena jer je 4 > 3
- ( 1 3 4 6 9 ) → ( 1 3 4 6 9 )
- ( 1 3 4 6 9 ) → ( 1 3 4 6 9 )
Treći prolaz:
- ( 1 3 4 6 9 ) → ( 1 3 4 6 9 )
- ( 1 3 4 6 9 ) → ( 1 3 4 6 9 )
- ( 1 3 4 6 9 ) → ( 1 3 4 6 9 )
- ( 1 3 4 6 9 ) → ( 1 3 4 6 9 )
Primetimo da je niz bio sortiran već nakon drugog prolaza, međutim, da bi se to utvrdilo, potrebno je bilo napraviti još jedan prolaz.
3. Insertion Sort (Sortiranje umetanjem)
Algoritam sortira niz tako što jedan po jedan element niza umeće na odgovarajuće mesto u do tada sortirani deo niza. Ako niz ima više od jednog elementa, sortiraj sve elemente ispred poslednjeg, a zatim umetni poslednji u taj sortirani podniz.
Iako ima kvadratnu vremensku složenost, često je kod kratkih nizova brži od naprednijih algoritama. Najgori slučaj nastupa kada je niz sortiran u obratnom redosledu.
Primer: Niz [12, 11, 13, 5, 6]
1. Uzimamo 11, poredimo sa 12. 11 < 12 -> [11, 12, 13, 5, 6]
2. Uzimamo 13, ostaje gde jeste -> [11, 12, 13, 5, 6]
3. Uzimamo 5, umećemo na početak -> [5, 11, 12, 13, 6]
4. Merge Sort (Sortiranje spajanjem)
Merge sort je algoritam zasnovan na strategiji "Podeli pa vladaj" (Divide and Conquer). On rekurzivno deli niz na dve polovine dok ne dođe do nivoa pojedinačnih elemenata, a zatim te elemente spaja u sortirane celine.
Ovaj algoritam je stabilan i garantuje vremensku složenost od O(n log n) u svim slučajevima, ali zahteva dodatni memorijski prostor za pomoćni niz.
Primer: Niz [38, 27, 43, 3]
1. Podeli: [38, 27] i [43, 3]
2. Podeli: [38], [27], [43], [3]
3. Spoji (sortirano): [27, 38] i [3, 43]
4. Finalno spoji: [3, 27, 38, 43]
5. Quick Sort (Brzo sortiranje)
Quick sort takođe koristi "Podeli pa vladaj" strategiju. Bira se jedan element koji se naziva pivot. Algoritam zatim raspoređuje ostale elemente tako da su svi manji od pivota levo, a svi veći desno od njega.
Ovaj proces se rekurzivno primenjuje na levu i desnu stranu. Iako mu je najgora složenost O(n2), u praksi je najčešće brži od Merge sorta jer radi "u mestu" bez potrebe za dodatnom memorijom.
Primer: Niz [10, 80, 30, 90, 40, 50, 70]
1. Pivot je 70.
2. Elementi manji od 70 idu levo: [10, 30, 40, 50].
3. Elementi veći od 70 idu desno: [80, 90].
4. Rezultat: [10, 30, 40, 50, 70, 80, 90].