Sadržaj
Razvrstavanje skupa stavki na popisu često je zadatak u programiranju. Često ljudsko biće može izvršiti taj zadatak intuitivno. Međutim, računalni program treba slijediti točan slijed uputa kako bi ga dovršio, a taj se niz zove algoritam. Algoritam za razvrstavanje je metoda koja se koristi za postavljanje popisa neorganiziranih stavki u određenom redoslijedu. Redoslijed redoslijeda određuje se ključem. Postoji nekoliko algoritama za sortiranje koji se razlikuju u pogledu učinkovitosti i performansi. Neke poznate i važne ove vrste uključuju: sortiranje mjehurića, sortiranje sortiranja, sortiranje umetanja i brzo sortiranje.
Bubble sort
Bubble sort opetovano mijenja susjedne elemente koji nisu u redu dok svaki popis stavki nije u nizu. Na taj način stavke variraju na popisu prema njihovim vrijednostima, najveće (u slučaju uzlaznog reda) koje završava na kraju svake iteracije.
Glavna prednost ovog algoritma je da je njegova implementacija jednostavna i poznata. Osim toga, u sorti s mjehurićima, elementi se zamjenjuju bez korištenja privremenog spremišta, što zahtijeva minimalni prostor. Glavni nedostatak je činjenica da ne pokazuje dobre rezultate kada popis sadrži mnoge stavke. To je zato što ova vrsta naručivanja zahtijeva n2 koraka obrade za svaki broj n elemenata koji će biti razvrstani. Stoga je sorta mjehurića naznačena za akademsku nastavu, ali ne i za stvarne aplikacije.
Vrsta odabira
Sortiranje odabira neprestano prelazi popis stavki odabirom jedne stavke odjednom i stavljanjem na ispravan položaj sekvence.
Glavna prednost sortne sorte je da dobro radi na malom popisu. Osim toga, budući da je to algoritam za naručivanje mjesta, ne treba mu privremeno spremanje izvan onoga što je potrebno za pohranu izvornog popisa. Glavni nedostatak je njegova niska učinkovitost u velikim popisima. Kao i sorta mjehurića, potrebno je n2 broj koraka za svaki n elemenata. Osim toga, na njegovu učinkovitost lako je utjecati početni redoslijed stavki prije postupka provjere. Zbog toga je ovaj tip odabira prikladan samo za popis gdje je nekoliko elemenata u slučajnom redoslijedu.
Vrsta umetanja
Sortiraj sortira popis više puta i svaki put umetne stavku neuređene sekvence u ispravan položaj.
Glavna prednost redoslijeda umetanja je njegova jednostavnost, kao i dobra izvedba na malim popisima. To je algoritam za naručivanje mjesta, tako da je prostorni zahtjev minimalan. Loša strana je u tome što ne funkcionira kao ni drugi algoritmi sortiranja. Uz n2 korake potrebne za rad, insert sort ne radi dobro s velikim popisima. Međutim, to je osobito korisno s popisima nekoliko stavki.
Brzo sortiranje
Brzo sortiranje radi s načelom podjele i osvajanja. Prvo, popis stavki dijeli na dva pod-popisa na temelju stožernog elementa. Svi elementi u prvom pod-popisu su raspoređeni tako da su manji od stožera, dok su svi elementi u drugom pod-popisu raspoređeni tako da budu veći od stožera. Isti proces particioniranja i organiziranja izvršava se više puta u rezultirajućim podlistama sve dok se ne organizira cijeli popis.
Brzo sortiranje neki smatraju najboljim algoritmom za sortiranje zbog njegove značajne prednosti u smislu učinkovitosti jer dobro funkcionira s velikim popisom stavki. Naručivanjem na licu mjesta također nema potrebe za dodatnim prostorom za pohranu. Mali nedostatak koji predstavlja predstavlja da je njegova najgora izvedba slična prosječnoj izvedbi ostalih gore opisanih algoritama. Međutim, važno je napomenuti da je ovaj najgori slučaj vrlo rijedak. Općenitije, brza sorta proizvodi najučinkovitiji i najrašireniji način organiziranja popisa bilo koje veličine.
