Sammenligning av Sorteringsalgoritmer

de fleste sorteringsalgoritmer fungerer ved å sammenligne dataene som sorteres. I noen tilfeller kan det være ønskelig å sortere en stor del data (for eksempel astruct som inneholder et navn og en adresse) basert på bare en del av disse dataene.Den delen av data som faktisk brukes til å bestemme den sorterte rekkefølgen kalles nøkkelen.
Sorteringsalgoritmer vurderes vanligvis av effektiviteten. I dette tilfellet refererer effektivitet til algoritmisk effektivitet som størrelsen på inngangen vokser stort og er generelt basert på antall elementer som skal sorteres. De fleste avalgoritmer i bruk har en algoritmisk effektivitet av Enten O (n^2) orO(n*log (n)). Noen få spesielle kasusalgoritmer (et eksempel er nevnt I Programmeringsperler) kan sortere visse datasett raskere Enn O(n*log (n)). Thesealgorithms er ikke basert på å sammenligne elementene som sorteres og stole påtricks. Det har blitt vist at ingen nøkkel-sammenligningsalgoritme kan utføre bedreenn O (n * log (n)).
Mange algoritmer som har samme effektivitet har ikke samme hastighet på samme inngang. Først må algoritmer vurderes basert på deres gjennomsnittlige case, best case og worst case effektivitet. Noen algoritmer,som rask sortering, utfører svært godt for noen innganger, men forferdelig for andre. Andrealgoritmer, for eksempel sammenslåing, påvirkes ikke av rekkefølgen på inndataene.Selv en modifisert versjon av boble sort kan fullføre I O (n) for de flestegunstige innganger.
en annen faktor er «konstant term». Som big – o notasjon abstracts bort mangeav detaljene i en prosess, er det ganske nyttig for å se på bigpicture. Men en ting som blir droppet ut er konstanten foran uttrykket: For Eksempel Er O (c * n)bare O (n). I den virkelige verden, c, vil variere på tvers av ulike algoritmer. En godt implementertquicksort bør ha en mye mindre konstant multiplikator enn heap sort.Et annet kriterium for å bedømme algoritmer er deres plassbehov-dothey krever skrapeplass eller kan arrayet sorteres på plass (uten ekstra minne utover noen få variabler)? Noen algoritmer krever aldriekstra plass, mens noen er lettest forstått når implementert medekstra plass(heap sort, for eksempel, kan gjøres på plass, men konseptueltdet er mye lettere å tenke på en egen haug). Plassbehov kan til og med avhenge av datastrukturen som brukes (slå sammen sortering på arrays versus slå sammen sortering onlinekoblede lister, for eksempel).
et tredje kriterium er stabilitet – bevarer sorteringen rekkefølgen av nøkler med like verdier? De fleste enkle sorter gjør nettopp dette, men noen slags, for eksempelbillig sort, ikke.
følgende diagram sammenligner sorteringsalgoritmer på de ulike kriteriene som er skissert ovenfor; algoritmene med høyere konstante vilkår vises først, skjønt dette er tydeligvis et implementeringsavhengig konsept og bør bare tas som en grov guide når du velger mellom slags samme big-o-effektivitet.