Algoritmi sortiranja

Algoritam sortiranja je algoritam  koji stavlja elemente liste u određenom redosledu. Najviše korišćena naređenja su numerički i leksičko-grafički red. Efikasno sortiranje je važno za optimizaciju korišćenja drugih algoritama (kao što su algoritmi pretrage i spajanja) koje zahtevaju unos podataka u sortirane liste; takođe je često korisno za "kanonizovane" podatake i za proizvodnju ljudski razumljivih izlaznih vrednosti. Formalnije rečeno, izlaz mora zadovoljiti dva uslova:

1. Izlaz je u rastućem redosledu (svaki element je veći od prethodnog elementa prema željenom redosledu);
2. Izlaz je permutacija (preuređena) ulaza.

Dalje, podaci se radije uzimaju da budu niz, koji omogućava nasumičan pristup, nego lista koja dozvoljava samo sekvencijalni pristup, mada često algoritmi se mogu primenjivati uz pogodnu modifikaciju za obe vrste podataka.

Od nastanka računarstva, problem sortiranja je privukao velika istraživanja, možda zbog složenosti njegovog efikasnog rešavanja uprkos svom jednostavnom obračun. Na primer, "mehurasto sortiranje" je analiziran već 1956. godine. Osnovna granica sortiranja poređenja algoritama je da oni zahtevaju vreme izvršavanja – O(n log n) – u najgorem slučaju, mada bolje performanse je moguće izvesti na stvarnim podacima (kao što su sortirani podaci), i algoritama koji nisu osnovani na poređenju, kao što je brojanje vrsti, mogu imati bolje performanse. Iako mnogi smatraju sortiranje kao rešen problem - asimptotično optimalni algoritmi su poznati još od sredine 20. veka – korisni novi algoritmi se još uvek prave sa sada već uveliko korišćenim timsort iz 2002. godine, i bibliotečko sortiranje koje se prvi put pojavilo 2006. godine.

Algoritmi sortiranja su rasprostranjeni u uvodu informatike, gde obilje algoritama za problem pruža blagi uvod u razne koncepte algoritma kao što su " veliko O", podeli pa vladaj algoritmi, strukture podataka kao što su gomile i binarna stabla, "slučajni algoritmi", analiza najbolji, najgori i prosečan slučaj, kompromisi vremenskog prostora, kao i gornja i donja granica.

Klasifikacija

Algoritmi sortiranja se često dele po:

• Kompleksnosti (najgore, prosečno i najbolje ponašanje) poređenja elemenata u smislu veličine liste (n). Za tipične algoritme sortiranja, dobro ponašanje je O(n log n), sa paralelnim sortiranjem je O(log2 n), a najgore je O(n²). (pogledaj "veliko O") Idealno ponašanje za serijsko sortiranje je O(n), ali ovo nije moguće u prosečnom slučaju. Najpovoljnije za paralelno sortiranje je O(log). Poređenje sortiranja algoritama, koje procenjuje elemente liste putem apstraktnog ključnog poređenja rada zahteva najmanje O (n log n) poređenja za većinu ulaznih vrednosti.
• Složenost razmene (za "na mestu" algoritama).
• Memorijska iskorišćenost (i korišćenje drugih računarskih resursa). Posebno, neki algoritmi za sortiranje su "na mestu". "Na mestu" vrste zahteva samo O (1) memorije izvan stavki koje su sortirane; Ponekad se O (log (n)) dodatne memorije smatra "na mestu".
• Rekurzija. Neki algoritmi su ili rekurzivni ili ne-rekurzivni, dok drugi mogu biti oba (npr. integrisano sortiranje).
• Stabilnost: stabilni algoritmi za sortiranje održe relativan red zapisa sa jednakim ključevima (tj. vrednostima).
• Bez obzira da li je to sortiranje poređenjem ili ne. Sortiranje poređenjem ispituje podatke samo poređenjem dva elementa sa operatorom poređenja.
• Opšti metod: umetanje, razmena, izbor, spajanje, itd. Sortiranje razmenom se sastoji iz mehurastog i brzog sortiranja. Selektivno sortiranje čine mešovito i nagomilano sortiranje. Takođe, tu se gleda da li je serijsko ili paralelno. Ostatak ove diskusije se gotovo isključivo koncentriše na serijske algoritme i serijski rad.
• Prilagodljivost: Da li preuređenost od ulaza utiče ili ne na vreme rada. Algoritmi koji se uzimaju u obzir su adaptivni.

Stabilnost

Primer stabilnog sortiranje na kartama. Kada su karte sortirane po rangu sa stabilnim sortiranjem, dve petice moraju ostati u originalnom redosledu, kao što su i ušle. Kada su sortirane sa nestabilnim sortiranjem, petice gube svoj originalni redosled.

Kada se sortira neka vrsta podataka, samo deo podataka se ispituje pri određivanju redosleda. Na primeru sa sortiranjem karata, u kartici sa desne strane se vid da su karte sortirane prema njihovom rangu, a njihova boja se ignoriše. Ovo daje mogućnost višestrukih različitih verzija sortiranja originalne liste. Algoritmi stabilnog sortiranja se prema sledećem pravilu: ako dve stavke uporedi kao jednake (kao što su dve karte petice) onda će njihov relativni redosled biti sačuvan, tako da ako jedna dođe pre ostalih, onda će i da izađe pre ostalih.

Formalnije rečeno, sortirani podaci mogu biti predstavljeni kao zapis ili kao vrednosti entorke, a deo podataka koji se koristi za sortiranje se zove ključ. U primeru sa kartama, karte su predstavljene kao vrednost (rang, iste boje) a ključ je rang. Algoritam za sortiranje je stabilan kad god postoje dve vrednosti P i S sa istim ključem, i P pojavi pre S u prvobitnom spisku, onda P ostaje ispred S u sortiranoj listi.

Stabilnost ne predstavlja problem kada se elementi mogu razlikovati, kao što je kod celih brojeva, ili uopšte svi podaci gde su svi elementi ključ, stabilnost ne predstavlja problem. Stabilnost takođe nije problem ako su svi ključevi različiti.

Nestabilni algoritmi sortiranja mogu biti prerađeni u stabilne. Jedan od načina da se to uradi je da se veštački produži poređenje ključeva, tako da poređenja između dva objekta sa jednakim ključevima koriste redosled unosa u originalnim ulaznoj listi kao u "taj-brejku". Međutim, pamćenje ove naredbe može da zahteva dodatno vreme i prostor.

Jedna aplikacija za stabilne algoritme sortiranja, sortira listu koristeći primarni i sekundarni ključ. Na primer, želimo da sortiramo karte iz ruke po bojama i to po redosledu: detelina (♣), karo (♦), srce (♥), pik (♠), a unutar svakog znaka, karte budu sortirane po rangu. Ovo se može uraditi tako što se prvo sortiraju karte po rangu (koristeći bilo kakvo sortiranje), a zatim radi stabilno sortiranje znakova:

Unutar svakog znaka, stabilno sortiranje čuva redosled po rangu, koje je već urađeno. Ova ideja se može proširiti na bilo koji broj ključeva, a urađeno je uz pomoć osnovnog sortiranja. Isti efekat se može postići i sa nestabilnim sortiranjem pomoću poređenja leksiko-grafičkih ključeva, koje na primer poredi prvo znakove, a zatim upoređuje po rangu ako su znakovi isti.

Poređenje algoritama

U ovoj tabeli, je n broj vrednosti koje treba da se sortiraju. Kolone "Prosečna" i "Najgora" daju složenost vremena u svakom slučaju, pod pretpostavkom da je dužina svakog ključa konstantna i da stoga sva poređenja, razmene i ostale potrebne operacije mogu da se nastave u konstantnom vremenu. "Memorija" označava količinu pomoćnog skladišta potrebnog za dalje korišćenje samog spiska, pod istom pretpostavkom. Lista zahteva vremena i memorije se smatra definisanim u okviru definicije "veliko O". Logaritmi su po bilo kom osnovu; oznaka  $\log ^{2}n$ znači $(\log n)^{2}$.

Ovo su sve poređenja sortiranja, pa se ne može izvršiti brže od O(n log n) u prosečnom i najgorem slučaju.

Poređenje sortiranja

Naziv	Najbolji	Prosek	Najgori	Memorija	Tabela	Metoda	Ostali podaci
Brzo sortiranje	15 !$n\log n$	20 !$n\log n$	25 !$n^{2}$	05 !$\log n$ prosek, najgori slučaj je $n$; "Sedvik" varijacija je $\log n$ najgori slučaj	tipično "na mestu" nije stabilno; stabilne verzije postoje	Podela	Brzo sortiranje se uglavnom izvršava "na mestu" sa O(log n) "stek" prostora. Većina implementacija su nestabilne, kako je stablo na mesto particionisanja složenije. Varijante Algoritma koriste O(n) mesta da sačuvaju particiju. Brza varijanta koristi trostruku (FAT) podelu uzima O (n) poređenja kada je sortiranje niz jednakih ključeva.
Spajanje	20 !$n\log n$	20 !$n\log n$	20 !$n\log n$	15 !$n$	Da	Spajanje	Visoko paralelizovano (up to O(log n) koristi tri Mađara algoritam ili praktičnije rečeno, Kolovo paralelno spajanje za obradu velike količine podataka.
"Na mestu" spajanje	—	—	23 !$n\log ^{2}n$	00 !$1$	Da	Spajanje	Može biti implementirano kao stabilno na osnovu stabilnog "na mestu" spajanja.
Nagomilano sortiranje	20 !$n\log n$	20 !$n\log n$	20 !$n\log n$	00 !$1$	Ne	Selekcija
Umetanje	15 !$n$	25 !$n^{2}$	25 !$n^{2}$	00 !$1$	Da	Umetanje	O(n + d), u najgorem slučaju preko sekvenci koje imaju d inverzije.
Unutrašnje sortiranje	20 !$n\log n$	20 !$n\log n$	20 !$n\log n$	05 !$\log n$	Ne	Podela i Selekcija	Koristi se u STŠ implementacijama.
Selektivno sortiranje	25 !$n^{2}$	25 !$n^{2}$	25 !$n^{2}$	00 !$1$	Ne	Selekcija	Stabilno sa O(n) dodatnog prostora, na primer pomoću liste.
" Timsort"	15 !$n$	20 !$n\log n$	20 !$n\log n$	15 !$n$	Da	Umetanje i Spajanje	Traži n poređenja kada su podaci već sortirani ili se obrnuto sortiraju.
Kubno sortiranje	15 !$n$	20 !$n\log n$	20 !$n\log n$	15 !$n$	Da	Umetanje	Traži n poređenja kada su podaci već sortirani ili se obrnuto sortiraju.
Sortiranje ljuske	15 !$n$	23 !$n\log ^{2}n$ or $n^{3/2}$	23 !Depends on gap sequence; best known is $n\log ^{2}n$	00 !$1$	Ne	Umetanje	Male veličina kod, bez upotrebe "steka", razumno brzo, korisno gde je memorija bitna kao što su ugrađene i starije aplikacije.
Mehurasto sortiranje	15 !$n$	25 !$n^{2}$	25 !$n^{2}$	00 !$1$	Da	Razmena	Veoma male veličine kod.
Binarno grananje	15 !$n$	20 !$n\log n$	20 !$n\log n~{\text{(balanced)}}$	15 !$n$	Da	Umetanje	Kada se koristi samobalansirajuće binarno stablo pretrage.
Kružno sortiranje	25 !$n^{2}$	25 !$n^{2}$	25 !$n^{2}$	00 !$1$	Ne	Umetanje	"Na mestu" sa teorijski optimalnim brojem unosa.
Skladištno sortiranje	15 !$n$	20 !$n\log n$	25 !$n^{2}$	15 !$n$	Da	Umetanje
Strpljivo sortiranje	15 !$n$	—	20 !$n\log n$	15 !$n$	Ne	Umetanje i Selekcija	Traži sve najduže rastuće podnizove u O(n log n).
Glatko sortiranje	15 !$n$	20 !$n\log n$	20 !$n\log n$	00 !$1$	Ne	Selekcija	Adaptivno sortiranje: $n$ poređenja kada se podaci već sortiraju i 0 razmene.
Štrand	15 !$n$	25 !$n^{2}$	25 !$n^{2}$	15 !$n$	Da	Selekcija
"Turnir"	20 !$n\log n$	20 !$n\log n$	20 !$n\log n$	15 !$n$	Ne	Selekcija	Varijanta nagomilanog sortiranja.
"Koktel"	15 !$n$	25 !$n^{2}$	25 !$n^{2}$	00 !$1$	Da	Razmena
Kombinovano	15 !$n$	15 !$n\log n$	25 !$n^{2}$	00 !$1$	Ne	Razmena	Kod male veličine.
Gnom	15 !$n$	25 !$n^{2}$	25 !$n^{2}$	00 !$1$	Da	Razmena	Kod veoma male veličine.
Nemešovito	15 !$kN$	25 !$kN$	25 !$kN$	00 !"Na mestu" za linkovane liste.	Ne	Distribucija i Spajanje	Ne izvode se razmene. Parametar 'k' je proporcionalan entropiji koja se unosi. K = 1 za određeno do napred ili otpozadi.
Frančinijev metod	—	20 !$n\log n$	20 !$n\log n$	00 !$1$	Da	?
Blokada	15 !$n$	20 !$n\log n$	20 !$n\log n$	00 !$1$	Da	Umetanje i Spajanje	Kombinuje se blok O(n) "na mestu" spaja algoritam sa odozdo prema gore spajanjem.
Neobično sortiranje	15 !$n$	25 !$n^{2}$	25 !$n^{2}$	00 !$1$	Da	Razmena	Može se lako pustiti u paralelne procese.

Sledeća tabela opisuje algoritme celobrojnog sortiranja i drugih algoritama za sortiranje koji ne koriste upoređivanje. Kao takvi, oni nisu ograničeni na $\Omega (n\log n)$ donju granicu. Pretpostavlja se da je složenost n stavki da se sortiraju, sa ključevima veličine k, cifre veličine d i r raspon brojeva koji treba da se sortiraju. Mnoge od njih su zasnovane na pretpostavci da je ključna veličina dovoljno velika da sve stavke imaju jedinstvene ključne vrednosti, a samim tim i da n << 2^k, gde<< znači "mnogo manje od".

Bez poređenja

Naziv	Najbolji	Prosek	Najgori	Memorija	Stabilan	n << 2k	Beleške
Pretinac	—	$n+2^{k}$	$n+2^{k}$	$2^{k}$	Da	Da
Segmentno(označeni ključevi)	—	$n+k$	$n^{2}\cdot k$	$n\cdot k$	Da	Ne	Postavlja ravnomernu raspodelu elemenata iz domena u nizu.
Segmentno(celobrojni ključevi)	—	$n+r$	$n+r$	$n+r$	Da	Da	Ako r je O(n), onda je Prosek O(n).
Brojenje	—	$n+r$	$n+r$	$n+r$	Da	Da	Ako r je O(n), onda je Prosek O(n).
LSD Osnovno	—	$n\cdot {\frac {k}{d}}$	$n\cdot {\frac {k}{d}}$	$n+2^{d}$	Da	Ne
MSD Osnovno	—	$n\cdot {\frac {k}{d}}$	$n\cdot {\frac {k}{d}}$	$n+2^{d}$	Da	Ne	Stabilna verzija koristi eksterni niz veličine n i drži sve stavke.
MSD Osnovno ("na mestu")	—	$n\cdot {\frac {k}{d}}$	$n\cdot {\frac {k}{d}}$	$2^{d}$	Ne	Ne	${\frac {k}{d}}$ nivo rekurzije, 2d za brojanje niza.
Razdvojeno sortiranje	—	$n\cdot {\frac {k}{d}}$	$n\cdot \left({{\frac {k}{s}}+d}\right)$	${\frac {k}{d}}\cdot 2^{d}$	Ne	Ne	Asymptotic are based on the assumption that n << 2k, but the algorithm does not require this.
Izbijanje	—	$n\cdot {\frac {k}{d}}$	$n\cdot {\frac {k}{d}}$	$n\cdot {\frac {k}{d}}$	Ne	Ne	Ima bolji konstantan faktor nego osnovno sortiranje za sortiranje niskih. Iako se donekle oslanja na specifičnosti često su se javljale niske.
"Fleš"	$n$	$n+r$	$n^{2}$	$n$	Može biti stabilan sa $O(n)$ dodatnim prostorom	Ne	Zahteva ravnomernu raspodela elemenata iz domena u niz da bi radio u linearnom vremenu. Ako je distribucija izuzetno mimoilazno onda može ići kvadratna ako je osnova kvadratna (obično je vrsta umetanje). "Na mestu" verzija nije stabilna.
"Poštar"	—	$n\cdot {\frac {k}{d}}$	$n\cdot {\frac {k}{d}}$	$n+2^{d}$	—	Da	Varijacija segmentnog, koji radi veoma slično MSD-u Osnovnog. Specifična za postavljanje potrebnih usluga.

Primerno sortiranje se može paralelno koristiti sa nekim sortiranjem koje ne koristi poređenje, i pritom efikasno distribuira podatke na više različitih segmenata i onda ih propušta dalje, sortirajući ih u nekoliko procesa bez potrebe da se ponovo dele jer su već međusobno sortirani.

Sledeća tabela opisuje neke algoritme za sortiranje koji su nepraktični za upotrebu u stvranoj situaciji zbog izuzetno lošeg učinka ili specijalizovanih hardverskih zahteva.

Naziv	Najbolji	Prosek	Najgori	Memorija	Stabilan	Poređenje	Ostali podaci
"Nišan"	15 !$n$	23 !$S$	23 !$S$	25 !$n^{2}$	N/A	Ne	Radi samo sa pozitivnim celim brojevima. Zahteva specijalizovan hardver za rad u zagarantovano O (n) vreme. Postoji mogućnost za implementaciju softvera, ali rad vremena će biti O (S), gde je S skup svih celih brojeva koji se sortiraju, u slučaju malih celih brojeva može se smatrati da je linearna.
Jednostavno sortiranje	—	15 !$n$	15 !$n$	05 !$\log n$	Ne	Da	Brojanje je broj prolaza.
Anketno	15 !$n$	15 !$n$	15 !$n$	25 !$n^{2}$	Da	Biranje	Ovo je linearno vremen, analogni algoritam za sortiranje niz stavki, zahtevajući O ( n ) stek prostora, a sortiranje je stabilno. Ovo zahteva n paralelnih procesa. Vidi Špagetno sortiranje.
Sortiranje mreže	06 !$\log ^{2}n$	06 !$\log ^{2}n$	06 !$\log ^{2}n$	21 !$n\log ^{2}n$	Razlikuje (mreže stabilnog sortiranja zahtevaju više poređenja)	Da	Redosled poređenja je unapred postavljen na osnovu određene veličine mreže. Nepraktično je za više od 32 artikla.
Bitonik poređenje	06 !$\log ^{2}n$	06 !$\log ^{2}n$	06 !$\log ^{2}n$	21 !$n\log ^{2}n$	Ne	Da	Efikasna varijacija Sortiranja mreže.
"Glupo" sortiranje	15 !$n$	99 !$n\cdot n!$	99 !$\infty$	00 !$1$	Ne	Da	Razna mešanja. Koristi se za primer same svrhe, kao i sortiranje u najgorem slučaju isteklog vremena.
Marioneta	30 !$n^{\log 3/\log 1.5}$	30 !$n^{\log 3/\log 1.5}$	30 !$n^{\log 3/\log 1.5}$	15 !$n$	Ne	Da	Sporije nego većina algoritama za sortiranje sa vremenom od složenosti O(nlog 3 / log 1.5 ) = O(n2.7095...).

Teorijski kompjuterski naučnici su detaljno pručili druge algoritme sortiranja koji omogućavaju bolje od O(n log n) kompleksnost vremena preuzimanja dodatnih ograničenja, uključujući:

• Hanov algoritam, deterministički algoritam za sortiranje ključeva iz oblasti konačne veličine, uzimajući O(n log log n) vremena i O(n) prostora.
  
• Torupov algoritam, nasumičan algoritam za sortiranje ključeva iz oblasti konačne veličine, uzimajući O(n log log n) vremena i O(n) prostora.
• Nasumični algoritam celobrojnog sortiranja zahteva vreme i O(n) mesta.
  

Popularni algoritmi sortiranja

Iako postoji veliki broj algoritama za sortiranje, u praktičnom implementacija nekoliko algoritama dominira. Sortiranje ubacivanjem se koristi za male skupove podataka, dok se za velike podatake postavlja asimptotski efikasno sortiranje koristi pre svega nagomilano, spajanjem ili brzo sortiranje. Efikasne implementacije uglavnom koristi hibridni algoritam, kombinovanjem asimptotski efikasan algoritam za ukupno sortiranje sa unosnim za male liste na dnu rekurzije. Visoko regulisane implementacije koriste sofisticiranije varijante, kao što su Timsort (spajajuće, unosno sortiranje i dodatna logika), koji se koristi u Androidu, Javi i Pajtonu, dok se uvodno (brzo i nagomilano sortiranje) koristi (u varijanti oblika) u nekim C++ sortiranjima implementacije i u . NET.

Za više ograničenih podataka, kao što su brojevi u fiksnom intervalu, u širokoj upotrebi su distribucijska sortiranja kao što su brojivo ili osnovno sortiranje. Mehurasto sortiranje i razne varijante se retko koriste u praksi, ali se često sreću u nastavi i teorijskim raspravama.

Za fizičko sortiranje objektata, kao što su alfabetizovani papiri (testovi ili knjige), ljudi intuitivno koriste uglavnom unosno sortiranje za male skupove. Za veće skupove, gde je prvi segment kao što je početnom slovo i višestruke segmente omogućava praktičnu sortiranje veoma velikih skupova. Često je prostor relativno jeftin, kao što je širenje objekata na podu ili na velikoj površini, ali operacije su skupe, posebno pomeranje predmeta velike udaljenosti - lokalitet referenca je važan. Spajanje je praktično za fizičke objekte, naročito može da se koristi kao dve ruke, po jedna za svaku listu da spoji, dok su ostali algoritmi kao što su nagomilavanje ili brzo sortiranje slabo pogodne za ljudsku upotrebu. Drugi algoritmi, kao što su skladištno ili varijanta unosnog sortiranja koja ostavlja prostor, takođe su praktični za fizičku korišćenje.

Jednostavno sortiranje

Dva najjednostavnija sortiranja su unosno i selektivno, oba su efikasna sa malim podatcima zbog malih troškova, ali nisu za velike podatake. Unosno sortiranje je generalno brže od selektivnog u praksi, zbog manjeg poređenja i dobre performanse na skoro sortiranim podatacima i zbog toga se preporučuje u praksi, ali selektivno se manje piše, i na taj način se koristi kada su performanse pisanja ograničavajući faktor.

Umetanje

Unosno sortiranje je algoritam jednostavnog sortiranja koji je relativno efikasan za male liste i uglavnom sortirane liste, i često se koristi kao deo sofisticiranijih algoritama. Radi po principu uzimanja elemenata iz liste jednog po jednog i postavljanja u njihov pravilan položaj u novoj sortiranoj listi. U nizovima, nova lista i preostali elementi mogu podeliti prostor niza, ali umetanje je skupo i zahteva pomeranje svih narednih elemenata zbog jednog. Sortiranje ljuske (vidi dole) je varijanta unosnog koji je efikasniji za veće liste.

Selekcija

Selektivno sortiranje je "na mestu" sortiranje poređenjem. Ima O(n²) kompleksnost, što ga čini neefikasnim za velike liste i generalno je lošiji od sličnog umetanja. Selektivno sortiranje je poznato po svojoj jednostavnosti, a takođe ima prednosti u performansama u odnosu na komplikovanije algoritme u određenim situacijama.

Algoritam pronalazi minimalnu vrednost, menja ga sa vrednošću na prvoj poziciji i ponavlja ove korake za ostatak liste. To ne čini ništa više od n zamena i na taj način je koristan kada je premeštanje veoma skupo.

Efikasno sortiranje

Praktično opšte sortiranje algoritama je skoro uvek zasnovano na algoritmu koji ima prosečnu složenost (i uopšte u najgorem slučaju) O(n log n), od kojih su najčešći su nagommilano, spajajuće i brzo sortiranje. Svaki ima svoje prednosti i mane, među kojima je najznačajnija jednostavna implementacija spajanja koja zahteva O(n) dodatnog prostora, a jednostavna implementacija brzog sortiranja ima O(n²) u najgorem slučaju složenosti. Ovi problemi se mogu rešiti ili ublažiti uz pomoć složenijeg algoritma.

Iako su ovi algoritmi asimptotski efikasni na slučajnim podacima, za praktičnu efikasnost na realnim podacima se koriste razne modifikacije. Prvo, granica ovih algoritama postaje značajna na manjim podacima, tako da se češće koristi hibridni algoritam, obično prelaženjem na umetanje kada su podaci dovoljno mali. Drugo, algoritmi se slabije koriste na već razvrstanim ili gotovo sortiranim podacima - to je uobičajeno u realnim podacima i mogu biti sortirani u O(n) vreme za odgovarajuće algoritme. Na kraju, oni mogu biti nestabilni, a stabilnost je često poželjna osobina u sortiranju. Često se koriste sofisticiraniji algoritmi, kao što su Timsort (na osnovu spajanja) ili unutrašnje (na osnovu brzog, vraćajući se u nagomilano sortiranje).

Spajanje

Ova vrsta ima prednost zbog lakoće spajanja već sortiranih listi u novu sortiranu listu. Počinje poređenjem svaka dva elementa (npr. 1 i 2, potom 3 i 4...) i zamene mesta ako je to potrebno. Onda spaja sve dobijene liste od po dva člana u četvoročlane liste i tako dalje; dok se poslednje dve liste sortirane u finalnu sortiranu listu. Od svih ovde opisanih algoritama, ovo je prva koja veoma dobro funkcionišu sa velikim listama, jer je njen najgori slučaj u vremenu O(n log n). Takođe se lako unosi u liste, ne samo u nizove, jer zahteva samo redni, a ne slučajan pristup. Međutim, ima dodatnu O(n) prostornu složenost, i uključuje veliki broj kopija u jednostavnim implementacijama.

Spajanje je relativno skoro dobilo na popularnosti za praktične implementacije, zbog njenog korišćenja u sofisticiranom algoritmu Timsort, koje se koristi za standardne metode sortiranja u programskim jezicima Pajton i Java (kao i JDK7). Spajanje je sama standarna rutina u Perl, između ostalog, i korišćena je u Javi barem od 2000. u JDK1.3.

Nagomilavanje

Nagomilavanje je mnogo efikasnija verzija od selekcije. Takođe, radi po principu određivanja najvećeg (ili najmanjeg) elementa u listi, stavljajući ga na kraj (ili početak) liste i nastavlja sa ostatkom liste, pri tom ostvaruje ovaj zadatak efikasno koristeći strukturu podataka zvanom "nagomilavanje", koja je posebna vrsta binarnog stabla. Kada je lista podataka napravljena, čvor je sigurno najveći (ili najmanji) element. Kada je uklonjena i stavljena na kraju liste, gomila je preuređena tako da je najveći elemenat preostalih poteza kod korena. Koristeći ovaj način, vreme za pretraživanje najvećeg člana je O(log n), umesto O(n) za linearno skeniranje kod selekcije. Ovo dozvoljava nagomilavanju O(n log n) vremena i ovo je ujedno i najgori mogući slučaj.

Brzo sortiranje

Brzo sortiranje je podeli pa vladaj algoritam koji se oslanja na particiju rada: na izabranu particiju niza elementa poznatijeg kao pivot. Svi elementi manji od pivota se stavljaju ispred njega i svi veće elementi iza njega. Ovo se može efikasno uraditi u linearnom vremenu i "na mestu". Manje i veće podliste su rekurzivno sortirane. Ovo daje prosečnu kompleksnost vremena O (n log n), sa niskim granicama i na taj način je ovo popularan algoritam. Efikasni implementacije brzog sortiranja (sa "na mestu" podelom) su obično nestabilne i pomalo složene, ali su među algoritmima najbrže sortiranje u praksi. Sa svojim skromnim O (log n) dodatnog prostora, brzo sortiranje je jedno od algoritama najpopularnijih sortiranja i najdostupnijih u standardnim programskim bibliotekama.

Za brzo sortiranje je važno da je najgori slučaj O(n²); što je retka pojava, u naivnim implementacijama (izbor prvi ili poslednji element kao pivot) se ovo često dešava zbog izdvojenih podataka. Najsloženiji problem je način odabira dobrog pivota, jer dosledno loši izbori stožera mogu dovesti do drastično sporijih O(n²) performansi, ali dobar izbor stožera daje O (n log n), koja je asimptotski odgovarajuća. Na primer, ako je na svakom koraku srednja vrednost izabrana kao stožer onda algoritam radi u O (n log n). Pronalaženje srednje vrednosti, kao što je kod srednje vrednosti selekcije algoritma je O (n) operacija na ne-sortiranim listama i samim tim uzima značajan deo granice sa sortiranjem. U praksi biranje slučajnog pivota gotovo sigurno daje O(n log) performanse.

Mehurasto sortiranje i varijante 

Mehurasto sortiranje i varijante kao što su "kokteli", su jednostavna, ali veoma neefikasna sortiranja. Oni se često mogu videti u uvodnim tekstovima i imaju neke teorijske interese zbog jednostavnosti analize, ali se retko koriste u praksi, a pre svega zbog rekreativnog interesa. Neke varijante poput sortiranja ljuske imaju otvorena pitanja o njihovom ponašanju.

Mehurasto sortiranje

Mehurasti algoritam za sortiranje ide kontinuirano kroz listu i menja stavke sve dok se ne pojave u ispravnom redosledu.

Mehurasto sortiranje je jednostavno sortiranje algoritma. Algoritam počinje na početku seta podataka. Upoređuje prva dva elementa i ako je prvi veći od drugog, onda im menja mesta. Ovim principom nastavlja da radi na svakom paru susednih elemenata do kraja seta podataka. Zatim ponovo počinje sa prva dva elementa, ponavljajući ovo sve dok ima potrebe za zamenom mesta elemenata. Prosek i najgori učinak ovog algoritma je O(n²), tako da se retko koristi za sortiranje velikih, nesređenih setova podataka. Mehurast princip se može koristiti za sortiranje malog broja stvari (gde asimptotska neefikasnost nije toliko bitna). Takođe se može efikasno koristiti na listi bilo koje dužine koja je skoro sortirana (to jest, elementi nisu značajno izmešani). Na primer, ako bilo koji broj elemenata je izvan svog mesta, pomoću samo jedne pozicije (npr. 0123546789 i 1032547698), mehurasto sortiranje će ih naći u prvom prolazu, a u drugom će ih postaviti na svoje mesto, tako da će trajati samo 2n.

Sortiranje ljuske

Ljuska se od mehura razlikuje po brojnim potezima, kojima premešta elemente na pozicije. 

Sortiranje ljuske je napravio Donald Šel 1959. Poboljšana mehurasto sortiranje i umetanje, uz pomoć obavljanja više funkcija premeštanja istovremeno. Jedna implementacija može se opisati kao uređenje sekvence podataka u dvodimenzionalnom nizu, a zatim sortiranje kolone niza koristeći umetanje.

Kombinovano sortiranje

Kombinovano sortiranje je jednostavan algoritam sortiranja, koji je dizajnirao Vlodcimrc Dobošievič 1980. Kasnije su ponovo otkrili i popularizovali Stefan Laci i Ričard Boks u Bajt Magazinu, u članku objavljenom aprila 1991. godine. Kombinovano sortiranje je pomoglo u poboljšanju mehurastog. Osnovna ideja je da se eliminišu "kornjače", to jest male vrednosti na kraju liste, jer je mehurasto sortiranje strahovito sporo. ("Zečevi", velike vrednosti koje se nalaze na početku liste, ne predstavljaju problem mehurastom sortiranju)

Distributivno sortiranje

Distributivno sortiranje se odnosi na bilo koji algoritam za sortiranje u kojem se podaci distribuiraju sa svog mesta na više srednjih struktura koje se onda okupljaju i štampaju. Na primer segmentno i "fleš" sortiranje su algoritmi za sortiranje zasnovani na bazi distribucije. Distributivni algoritam sortiranja se može koristiti u jednom procesu ili može biti distribuirani algoritam, gde se pojedinačne podgrupe odvojeno sortiraju u različitim procesima, pa onda kombinuju. Ovo omogućava spoljno sortiranje podataka koji su preveliki da bi stali u memoriju jednog računara.

Brojanje

Brojanje se primenjuje kada se svaki za ulaz zna da pripada određenom sklopu S mogućnosti. Algoritam radi u O(|S| + n) vremenu i O(|S|) memoriji gde je n dužina unosa. Radi stvaranjem celobrojnog niza veličine |S| i koristi i-ti broj da izbroji slučajeve i-tog člana S sklopa. Svaki ulaz je izračunat od strane uvećanih vrednosti odgovarajućeg sklopa. Nakon toga, brojanje niza se izvršava kroz petlju kako bi se sve vrednosti poređale. Ovaj algoritam se često ne može koristiti, jer S mora da bude razumno mali da bi algoritam bio efikasan, ali je izuzetno brz i pokazuje asimptotsko ponašanje kako se n povećava. On takođe može biti modifikovan da omogućava stabilno ponašanje.

Segmentno sortiranje

Segmentno sortiranje je Podeli pa vladaj algoritam sortiranja koji uopštava brojanje deljenjem niza u konačan broj segmenata. Svaki segment je sortiran pojedinačno ili koristeći drugi algoritam sortiranja ili rekurzivno primenom segmentnog algoritma.

Segmentno sortiranje najbolje radi kada su elementi skupa podataka ravnomerno raspoređeni po svim segmentima.

Osnovno sortiranje

Osnovno sortiranje je algoritam koji sortira brojeve preradom pojedinačne cifre. Brojevi n koji se sastoje od k cifara se sortiraju u O(n · k) vremenu. Ova vrsta sortiranja može da preradi cifre svakog broja ili počev od cifre najmanjeg značaja (LSD) ili počev od najznačajnije cifre (MSD). LSD algoritam prvo sortira spisak prema cifri najmanjeg značaja čuvajući njihov relativni redosled koristeći stabilno sortiranje. Onda sortira sledeću cifru i tako dalje, sve dok se spisak ne sortira od najmanje značajne do najznačajnije cifre. Dok LSD zahteva korišćenje stabilnog sortiranja, MSD algoritam to ne traži (osim ako je stabilno sortiranje poželjno). "Na mestu" MSD sortiranje nije stabilno. To je uobičajeno za brojanje da bude interno korišćeno od strane osnovnog. Hibridno sortiranje pristupa kao i korišćenje umetanja za male sklopove podataka pri čemu se značajno poboljšavaju performanse osnovnog sortiranja.

Obrasci korišćenja memorije i sortiranje indeksa

Kada je veličina niza za sortiranje približna ili premašuje raspoloživu primarnu memoriju, tako da (mnogo sporije) disk ili razmena prostora mora biti zauzeta, obrazac upotrebe memorije algoritma postaje važan i algoritam koji može biti prilično efikasan kada je niz lako uklapa u RAM, može da postane nepraktičan. U ovoj situaciji, ukupan broj poređenja postaje (relativno) manje važan, a broj delova iz memorije i sa diska koji se mora kopirati ili zameniti mogu da dominiraju performanse karakteristične algoritmu. Tako broj prolaza i lokalizacija poređenja može biti važniji od sirovog broja poređenja, jer se poređenja okolnih elemenata jedan sa drugim obavljaju u magistralama (ili u keš memoriji, čak i pri brzini procesora), što je u odnosu na brzinu diska praktično gledano trenutna.

Na primer, popularno rekurzivno brzo sortiranje daje prilično razumne performanse sa adekvatnim RAM-om, ali zbog rekurzivnog načina da se kopiraju delovi niza, postaje manje praktično kada se niz ne uklapa u RAM, jer to može izazvati niz sporih postupaka sa diska. U tom slučaju, može biti poželjan, čak i ako je potrebno više ukupnih poređenja.

Jedan od načina da se reši ovaj problem koji radi dobro kada su kompleksni zapisi (kao što je u relacionoj bazi podataka) koji su sortirani prema malom polju ključa da se stvori indeks u nizu, a zatim sortiranje indeksa umesto celog niza. (Sortirana verzija celog niza onda se može odjednom odštampati čitajući iz indeksa, ali često ni to nije neophodno, jer je indeks adekvatno sortiran) Budući da je indeks mnogo manji od celog niza, može se lako uklopiti u memoriju u koju ceo niz ne bi, efikasno eliminiše problem sa zamene-diska. Ovaj postupak se naziva "označavanje".

Druga tehnika za prevazilaženje problema memorije veličine je da se kombinuju dva algoritma na način koji uzima prednosti od oba da bi došlo do poboljšanja ukupne performanse. Na primer, niz može biti podeljen na delove veličine koji se uklapaju u RAM, sadržaj svakog dela se sortira korišćenjem efikasnog algoritma (kao što je brzi algoritam), a rezultati se spoje pomoću k-načina slično onoj proceduri koja se koristi kod spajanja. Ovo je brže od obavljanja spajanja ili brzog sortiranja za celu listu.

Tehnike se mogu kombinovati. Za sortiranje veoma velikih skupova podataka koji u velikoj meri prelaze sistemsku memoriju, čak i indeks možda treba da se sortira pomoću algoritma ili kombinacije algoritama dizajniranih da razumno nastupe sa virtuelnom memorijom, odnosno da se smanji potrebna količina zamene.

Neefikasna sortiranja

Neki algoritmi su spori u poređenju sa već gore diskutovanim algoritmima, kao što je "glupo" sortiranje O(n!) i "marioneta" O(n^2.7).

Povezani algoritmi 

Povezani problemi uključuju i delimično sortiranje (sortiranje samo k najmanjeg elementa liste, ili alternativno izračunavanja k najsitnijih elemenata, ali neuređeno) i selekcija (prebrojavanje k najmanjih elemenata). Ovo se može neefikasno rešiti totalnim sortiranjem, ali postoje efikasniji algoritmi, često dobijeni uopštavanjem algoritma za sortiranje. Najznačajniji primer je brza selekcija, koja je srodna brzom sortiranju. Nasuprot tome, neki algoritmi sortiranja mogu da budu izvedeni ponovnom primenom selekcije algoritma; brzo i brzo selektivno se mogu posmatrati kao suprotni potezi, jer se razlikuju samo u tome da li se primenjuje na obe strane (brzo sortiranje, podeli pa vladaj) ili na jednu stranu (brzo-selektivno, smanji i vladaj)

Suprotna vrsta od algoritma za sortiranje je algoritam mešanja. Ovo je fundamentalno drugačije, jer zahtevaju izvor slučajnih brojeva. Zanimljivo je da mešanja može da sprovodi algoritam za sortiranje, naime slučajnim sortiranjem: dodeljivanje slučajnog broja svakom elementu liste a zatim sortiranje na osnovu slučajnih brojeva. Ovo se obično ne sprovodi u praksi, međutim i tu je poznat jednostavan i efikasan algoritam za mešanje: Fišer-Jetsov mešač.

Algoritmi sortiranja su takođe dati za paralelne računare. Ovi algoritmi mogu biti pokrenuti u jednom toku uputstva za višestruke podatke računara. Habermanovo komšijski paralelno sortiranje sortira k elemente koristeći k procese u k koraka. Ovaj članak uvodi optimalne algoritme za paralelne računare gde se rk elementi sortiraju pomoću k procesa u k koracima.

Vidi još

• Upoređivanje
• Sortiranje mreža (upoređivanjem)
• "Švarcian" transformacija
• Algoritmi pretraživanja
• Kvantno sortiranje
• Glupi sort
• Podeli pa vladaj (informatika)

Literatura

• Goodrich, Michael T.; Tamassia, Roberto. „4.5 Bucket-Sort and Radix-Sort”. Algorithm Design Foundations, Michael T. Goodrich & Roberto. 
• Wirth, Niklaus (1986). Algorithms & Data Structures. Upper Saddle River, NJ: Prentice-Hall. ISBN 978-0-13-022005-9. 
• Knuth, Donald E. (1998). Sorting and Searching. The Art of Computer Programming. 3 (2nd izd.). Boston: Addison-Wesley. ISBN 978-0-201-89685-5. 
• Knuth, D. E. The Art of Computer Programming Volume 3: Sorting and Searching (3rd izd.). Addison-Wesley Professional. ISBN 978-0-201-48541-7. 
• Press, William H.; Flannery, Brian P.; Teukolsky, Saul A.; Vetterling, William T. (1992). Numerical Recipes in C: The Art of Scientific Computing (Second izd.). Cambridge University Press. ISBN 978-0-521-43108-8. 
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms (Third izd.). The MIT Press. ISBN 978-0-262-03384-8. 

Spoljašnje veze

• Sorting Algorithm Animations - Grafička ilustracija kako različiti algoritmi koriste različite vrste setova podataka.
• Sequential and parallel sorting algorithms Arhivirano na sajtu Wayback Machine (13. decembar 2012) - Objašnjenja i analize mnogih algoritama za sortiranje.
• Dictionary of Algorithms, Data Structures, and Problems - Rečnik algoritama, tehnika, zajedničkih funkcija, i problema.
• Slightly Skeptical View on Sorting Algorithms Razmatra nekoliko klasičnih algoritama i promoviše alternative "brzo sortirajućeg" algoritma.
• 15 Sorting Algorithms in 6 Minutes (Youtube) Vizuelizacija i "audizacija" 15 algoritama sortiranja za 6 minuta.
• A036604 sequence in OEIS database titled "Sorting numbers: minimal number of comparisons needed to sort n elements" koji obavljaju Ford-Džonsonovi algoritmi.
• Metode sortiranja nizova
• Poređenje algoritama sortiranja