I databehandling og matematikk er en sorteringsalgoritme en algoritme som setter elementer i en liste eller en vektor i en sekvens gitt av en ordensrelasjon , det vil si at utdataresultatet må være en permutasjon - eller omorganisering - av inngangen som tilfredsstiller den gitte ordreforhold. De mest brukte ordensrelasjonene er numerisk rekkefølge og leksikografisk rekkefølge . Effektive sorteringer er viktige for å optimalisere bruken av andre algoritmer (som søk og sammenslåing) som krever ordnede lister for rask utførelse. Det er også nyttig for å sette data i kanonisk form og for å generere utdata som kan leses av mennesker.
Siden begynnelsen av databehandlingen har bestillingsproblemet tiltrukket seg mye forskning, kanskje på grunn av kompleksiteten i å løse det effektivt til tross for sin enkle og kjente tilnærming. For eksempel har BubbleSort vært diskutert siden 1956. [ 1 ] Selv om mange kanskje anser det som et løst problem, fortsetter nye og nyttige sorteringsalgoritmer å bli oppfunnet frem til i dag (for eksempel ble bibliotekssortering først publisert i 2004). Sorteringsalgoritmer er vanlige i introduksjonstimer i informatikk, hvor overfloden av algoritmer for problemet gir en skånsom introduksjon til variasjonen av kjernekonsepter for algoritmer, slik som O-notasjon med stor bokstav , dele-og-hersk-algoritmer , datastrukturer , verste, beste. , og gjennomsnittlig kasusanalyse , og nedre grenser.
Sorteringsalgoritmer kan klassifiseres på følgende måter:
Algoritmer kjennetegnes av følgende egenskaper:
Stabile sorteringsalgoritmer opprettholder en relativ total forhåndsbestilling . Dette betyr at en algoritme er stabil bare når det er to poster R og S med samme nøkkel og med R foran S i den opprinnelige listen.
Når elementene er de samme (ikke skilles fra hverandre), for eksempel heltall, eller mer generelt, en hvilken som helst datatype der heltallselementet er nøkkelen, er ikke stabilitet et problem. Det antas imidlertid at følgende tallpar skal sorteres etter deres første komponent:
(4, 1) (3, 7) (3, 1) (5, 6)I dette tilfellet er to forskjellige resultater mulig, hvorav ett opprettholder en relativ rekkefølge av poster med like nøkler, og ett der det ikke gjør det:
(3, 7) (3, 1) (4, 1) (5, 6) (rekkefølgen opprettholdes) (3, 1) (3, 7) (4, 1) (5, 6) (rekkefølge endret)Ustabile sorteringsalgoritmer kan endre den relative rekkefølgen til poster med de samme nøklene, men stabile algoritmer gjør det aldri. Ustabile algoritmer kan implementeres spesielt for å være stabile. En måte å gjøre dette på er å kunstig utvide nøkkelmatching, slik at sammenligninger mellom to objekter med like nøkler avgjøres ved å bruke den opprinnelige inndatarekkefølgen. Å huske denne rekkefølgen mellom to objekter med samme nøkler er en upraktisk løsning, siden det vanligvis fører til ekstra lagring.
Sortering på primær-, sekundær-, tertiærnøkkel osv. kan gjøres ved hjelp av en hvilken som helst sorteringsmetode, og tar alle nøkler i betraktning (med andre ord ved å bruke en enkelt sammensatt nøkkel). Hvis en bestillingsmetode er stabil, er det mulig å bestille flere varer, hver gang med en annen nøkkel. I dette tilfellet må nøklene brukes i rekkefølge med økende prioritet.
Eksempel: bestill tallpar ved å bruke begge verdiene
(4, 1) (3, 7) (3, 1) (4, 6) (original) (4, 1) (3, 1) (4, 6) (3, 7) (etter å ha blitt sortert etter den andre verdien) (3, 1) (3, 7) (4, 1) (4, 6) (etter å ha blitt sortert etter første verdi)For det andre:
(3, 7) (3, 1) (4, 1) (4, 6) (etter å ha blitt sortert etter første verdi) (3, 1) (4, 1) (4, 6) (3, 7) (etter å ha blitt sortert etter den andre verdien, rekkefølgen etter den første verdien er forstyrret)En sorteringsalgoritme er naturlig når du prøver å sortere elementer i en ordnet eller nesten-ordnet liste, forbedrer utførelsestiden betraktelig. Det vil si at den innser at elementene er ordnet og ikke utfører unødvendige operasjoner. Det tydeligste eksemplet finnes i Enhanced Bubble-sorteringsmetoden, som avslutter prosessen når den avsluttes med ett pass og fastslår at det ikke var noen utvekslinger. Ikke så utvalgsalgoritmen som utfører alle passeringene likt uavhengig av om elementene i listen er ordnet eller ikke.
Noen sorteringsalgoritmer gruppert etter stabilitet og tar hensyn til beregningskompleksiteten .
| stabil | ||||
| oversatt navn | Opprinnelig navn | Kompleksitet | Hukommelse | Metode |
| boble sortering | boblesort | ELLER ( n² ) | ELLER (1) | Utveksling |
| Toveis boblesortering | cocktail sortering | ELLER ( n² ) | ELLER (1) | Utveksling |
| Innsettingssortering | Sett inn sortering | ELLER ( n² ) | ELLER (1) | Innsetting |
| Sortering etter bokser | bøtte sortering | O ( n ) | O( n ) | ikke sammenlignende |
| Sorter etter kontoer | Tellesortering | ELLER ( n + k ) | ELLER( n + k ) | ikke sammenlignende |
| Slå sammen sortering | slå sammen sortering | O ( n logg n ) | O ( n ) | Blanding |
| Sorter med binært tre | Binær tresortering | O ( n logg n ) | O( n ) | Innsetting |
| Duehull sortering | ELLER ( n + k ) | O( k ) | ||
| Radix Sort | radixsort | Eller ( nk ) | O( n ) | ikke sammenlignende |
| distribusjonsort | O ( n³ ) rekursiv versjon | ELLER( n² ) | ||
| gnomesort | ELLER ( n² ) | ELLER (1) | ||
| ustabil | ||||
| oversatt navn | Opprinnelig navn | Kompleksitet | Hukommelse | Metode |
| Skall sortering | skjellsort | ELLER ( n 1,25 ) | ELLER (1) | Innsetting |
| Kam sortering | O ( n logg n ) | ELLER (1) | Utveksling | |
| Utvalgssortering | Utvalgsort | ELLER ( n² ) | ELLER (1) | Utvalg |
| Heap Sorter | heapsort | O ( n logg n ) | ELLER (1) | Utvalg |
| smoothsort | O ( n logg n ) | ELLER (1) | Utvalg | |
| rask sortering | kvikksortering | Gjennomsnitt: O ( n log n ), verste tilfelle: O( n ²) |
O ( pålogging ) | skillevegg |
| Flere unike sorter | Gjennomsnitt: O ( n u), verste tilfelle: O( n ²); u=n; u = unikt antall poster |
|||
| tvilsom, upraktisk | ||||
| oversatt navn | Opprinnelig navn | Kompleksitet | Hukommelse | Metode |
| bogosort | Eller ( n × n !), verre: slutter ikke | |||
| pannekakebestilling | pannekakesortering | O ( n ), unntatt på Von Neumann-maskiner |
||
| Tilfeldig rekkefølge | tilfeldig sortering | Snitt: O(n!) Verst: Fullfører ikke | ||