Sammenligning av sorteringsalgoritme

Med bokstavelig talt dusinvis av sortering algoritmer tilgjengelige, bestemme hvilke vil fungere best med systemet vil avhenge av sammenligninger av flere faktorer, såsom størrelsen på listen, hastigheten eller kompleksitet av algoritmen, og hvorvidt man skal bruke en nøkkel for å sortere.

kompleksitet

Kompleksiteten av en sorteringsalgoritme måles ved hjelp av O (n), eller "orden n", hvor n er størrelsen av listen. Den måler hvor mange går det tar å sortere listen og beregner sitt beste, verste og gjennomsnittlig tid til å gjøre det. Vanlige kompleksiteten inkluderer n som best case for typer som for eksempel innsetting av slag og skallet slag, n log n, (ved bruk av en base-2 logaritmen, ikke en base-10), som er kompleksiteten for flettingen sortere og heapsort, og n², som er langsommere enn den første gang, og er hastigheten for utvalget slag.

List tilstand

Noen ganger vil du vite hvordan usorterte elementer i en liste er organisert: For eksempel om de er nesten sortert i omvendt rekkefølge, eller en liste med noen unike elementer. Slik kunnskap hjelper deg å velge en effektiv algoritme for å sortere det. For eksempel bruker innsetting liksom å sortere en liste i omvendt rekkefølge har en driftstid på n², mens haug liksom kan gjøre det raskere, i n log n gang. På en liste som er nesten sortert, er innsetting sort raskere enn haug slag. Når listen inneholder en fullstendig randomisert sett av data, velger en algoritme med en gjennomsnittlig saks kompleksitet n log n kjører tid, for eksempel haug slag, quicksort eller flettesortering.

Listestørrelse

Noen algoritmer er vanskeligere å bruke enn andre, slik at antall elementer i en liste, og hvor ofte du trenger å sortere kan bidra til å bestemme algoritmen du vil velge. Sorterer som innsetting typen er rask og fungerer godt når sortering mindre lister, og er enkel å implementere, men de er trege med større lister. Sorterer som bruker en splitt-og-hersk-algoritme som quicksort og flettesortering er vanskeligere å gjennomføre, men de liksom større lister raskere i gjennomsnitt tilfeller.

Stabilitet

Algoritmen stabilitet beskriver om sorteringsopprettholder rekkefølgen av elementer basert på en sorteringsnøkkel. For eksempel bruker det første tegnet som en nøkkel for en liste som har "John", "Steve" og "Jim" i den rekkefølgen, en stabil algoritme sorterer listen til "John", "Jim" og "Steve", mens en ustabil algoritme kan eller ikke kan sortere "Jim" før "John". Flettesortering, innsetting sortere og boblesortering er alle stabile algoritmer mens skallet form, utvelgelse sortere og heap liksom ikke.