Sorteringsalgoritme - Sorting algorithm

Inden for datalogi er en sorteringsalgoritme en algoritme, der sætter elementer i en liste i en rækkefølge . De mest anvendte ordrer er numerisk rækkefølge og leksikografisk rækkefølge , og enten stigende eller faldende. Effektiv sortering er vigtig for at optimere effektiviteten af andre algoritmer (f.eks. Søge- og flettealgoritmer ), der kræver, at inputdata er i sorterede lister. Sortering er også ofte nyttig til kanonikalisering af data og til fremstilling af output, der kan læses af mennesker.

Formelt skal output fra enhver sorteringsalgoritme opfylde to betingelser:

1. Outputtet er i monoton rækkefølge (hvert element er ikke mindre/større end det forrige element i henhold til den krævede rækkefølge).
2. Outputtet er en permutation (en genbestilling, men alligevel bevarer alle de originale elementer) af input.

For optimal effektivitet bør inputdataene gemmes i en datastruktur, der tillader tilfældig adgang frem for en, der kun tillader sekventiel adgang .

Historie og begreber

Fra begyndelsen af ​​computing har sorteringsproblemet tiltrukket megen forskning, måske på grund af kompleksiteten i at løse det effektivt på trods af det enkle, velkendte udsagn. Blandt forfatterne til tidlige sorteringsalgoritmer omkring 1951 var Betty Holberton , der arbejdede med ENIAC og UNIVAC . Boblesortering blev analyseret allerede i 1956. Asymptotisk optimale algoritmer har været kendt siden midten af ​​det 20. århundrede - nye algoritmer bliver stadig opfundet, hvor den meget udbredte Timsort stammer fra 2002, og bibliotekssorten blev først udgivet i 2006.

Sammenligningssorteringsalgoritmer har et grundlæggende krav om Ω ( n log n ) sammenligninger (nogle indgangssekvenser kræver et multiplum af n log n sammenligninger, hvor n er antallet af elementer i arrayet, der skal sorteres). Algoritmer, der ikke er baseret på sammenligninger, såsom tællesortering , kan have bedre ydeevne.

Sorteringsalgoritmer er udbredt i indledende datalogi -klasser, hvor overflod af algoritmer til problemet giver en skånsom introduktion til en række kernealgoritmebegreber, såsom stor O -notation , opdel og erobre algoritmer , datastrukturer såsom dynger og binære træer , randomiserede algoritmer , bedste, værste og gennemsnitlige tilfælde analyse, tid-rum afvejninger og øvre og nedre grænser .

At sortere små arrays optimalt (i mindst antal sammenligninger og swaps) eller hurtigt (dvs. under hensyntagen til maskinspecifikke detaljer) er stadig et åbent forskningsproblem, med løsninger kun kendt for meget små arrays (<20 elementer). Tilsvarende er optimal (ved forskellige definitioner) sortering på en parallel maskine et åbent forskningsemne.

Klassifikation

Sorteringsalgoritmer kan klassificeres efter:

• Beregningskompleksitet
  • Bedste, værste og gennemsnitlige sagsadfærd med hensyn til listens størrelse. For typiske serielle sorteringsalgoritmer er god opførsel O ( n  log  n ), med parallelsortering i O (log ²  n ), og dårlig opførsel er O ( n ² ). Ideel opførsel for en seriel sortering er O ( n ), men dette er ikke muligt i det gennemsnitlige tilfælde. Optimal parallelsortering er O (log  n ).
  • Swaps for "in-place" algoritmer.
• Hukommelsesbrug (og brug af andre computerressourcer). Især nogle sorteringsalgoritmer er " på plads ". Strengt taget behøver en på stedet sortering kun O (1) hukommelse ud over de elementer, der sorteres; undertiden O (log  n ) ekstra hukommelse betragtes som "på plads".
• Rekursion: Nogle algoritmer er enten rekursive eller ikke-rekursive, mens andre kan være begge dele (f.eks. Flettesortering).
• Stabilitet: stabile sorteringsalgoritmer opretholder den relative rækkefølge af poster med lige nøgler (dvs. værdier).
• Uanset om de er en sammenligningssort eller ej . En sammenligningssortering undersøger kun dataene ved at sammenligne to elementer med en sammenligningsoperator.
• Generel metode: indsættelse, udveksling, markering, fletning osv. Udvekslingssorter omfatter boblesortering og kviksort. Udvælgelsessorter omfatter cyklussortering og dyngsort.
• Uanset om algoritmen er seriel eller parallel. Resten af ​​denne diskussion koncentrerer sig næsten udelukkende om serielle algoritmer og forudsætter seriel drift.
• Tilpasningsevne: Uanset om indgangssortensitet påvirker spilletiden eller ej. Algoritmer, der tager højde for dette, vides at være adaptive .
• Online: En algoritme som Insertion Sort, der er online, kan sortere en konstant inputstrøm.

Stabilitet

Et eksempel på stabil sortering på spillekort. Når kortene er sorteret efter rang med en stabil sortering, skal de to 5'ere forblive i samme rækkefølge i det sorterede output, som de oprindeligt var i. Når de er sorteret med en ikke-stabil sortering, kan 5'erne ende i det modsatte rækkefølge i det sorterede output.

Stabile sorteringsalgoritmer sorterer lige elementer i samme rækkefølge, som de vises i input. For eksempel i kortsorteringseksemplet til højre sorteres kortene efter deres rang, og deres kulør ignoreres. Dette giver mulighed for flere forskellige korrekt sorterede versioner af den originale liste. Stabile sorteringsalgoritmer vælger en af ​​disse i henhold til følgende regel: hvis to elementer sammenlignes som lige (som de to 5 kort), så bevares deres relative rækkefølge, dvs. hvis det ene kommer foran det andet i input, kommer det før den anden i output.

Stabilitet er vigtig for at bevare orden over flere sorter på det samme datasæt . Sig f.eks., At elevposter bestående af navn og klassesektion er sorteret dynamisk, først efter navn, derefter efter klassesektion. Hvis der bruges en stabil sorteringsalgoritme i begge tilfælde, ændrer sorterings-efter-klasse-sektionsoperationen ikke navnrækkefølgen; med en ustabil sortering, kan det være, at sortering efter sektion blander navnrækkefølgen, hvilket resulterer i en ikke -alfabetisk liste over elever.

Mere formelt kan de data, der sorteres, repræsenteres som en post eller værdistørrelse, og den del af dataene, der bruges til sortering, kaldes nøglen . I korteksemplet er kort repræsenteret som en rekord (rang, kulør), og nøglen er rangen. En sorteringsalgoritme er stabil, hvis når der er to poster R og S med den samme nøgle, og R vises før S i den originale liste, så vil R altid vises før S i den sorterede liste.

Når lige elementer ikke kan skelnes, f.eks. Med heltal eller mere generelt alle data, hvor hele elementet er nøglen, er stabilitet ikke et problem. Stabilitet er heller ikke et problem, hvis alle nøgler er forskellige.

Ustabile sorteringsalgoritmer kan specielt implementeres for at være stabile. En måde at gøre dette på er at kunstigt udvide nøglesammenligningen, så sammenligninger mellem to objekter med ellers lige nøgler afgøres ved hjælp af rækkefølgen af ​​posterne i den originale inputliste som en tie-breaker. At huske denne ordre kan dog kræve ekstra tid og plads.

En applikation til stabile sorteringsalgoritmer er at sortere en liste ved hjælp af en primær og sekundær nøgle. Antag for eksempel, at vi ønsker at sortere en hånd med kort, så dragterne er i rækkefølgen køller (♣), diamanter ( ♦ ), hjerter ( ♥ ), spar (♠), og inden for hver kulør er kortene sorteret efter rang. Dette kan gøres ved først at sortere kortene efter rang (ved hjælp af enhver slags) og derefter lave en stabil sortering efter kulør:

Inden for hver kulør bevarer den stabile sortering den rækkefølge, der allerede var foretaget. Denne idé kan udvides til et vilkårligt antal nøgler og bruges ved radix -sortering . Den samme effekt kan opnås med en ustabil sortering ved hjælp af en leksikografisk nøglesammenligning, som f.eks. Først sammenligner med kulør og derefter sammenligner med rang, hvis dragterne er de samme.

Sammenligning af algoritmer

I disse tabeller er n antallet af poster, der skal sorteres. Kolonnerne "Bedste", "Gennemsnit" og "Værste" giver tidskompleksiteten i hvert tilfælde under den antagelse, at længden af ​​hver nøgle er konstant, og derfor kan alle sammenligninger, swaps og andre operationer fortsætte i konstant tid. "Hukommelse" angiver mængden af ​​ekstra lagerplads, der er nødvendig ud over det, der bruges af selve listen, under samme antagelse. Kørselstiderne og de angivne hukommelseskrav er inde i stor O -notation , derfor betyder logaritmernes basis ikke noget. Notation log ² n betyder (log n ) ² .

Sammenligningssorter

Nedenfor er en tabel med sammenligningssorter . En sammenligningssort kan ikke udføre bedre end O ( n log n ) i gennemsnit.

Sammenligningssorter

Navn	Bedst	Gennemsnit	Værst	Hukommelse	Stabil	Metode	Andre noter
Quicksort	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle n^{2}}$	${\ displaystyle \ log n}$	Ingen	Partitionering	Quicksort udføres normalt på stedet med O (log n ) stakplads.
Flet sorter	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	n	Ja	Fletning	Meget paralleliserbar (op til O (log n ) ved hjælp af de tre ungarers algoritme).
Fletningssort på stedet	-	-	${\ displaystyle n \ log ^{2} n}$	1	Ja	Fletning	Kan implementeres som en stabil sortering baseret på stabil sammenlægning på stedet.
Introsort	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle \ log n}$	Ingen	Opdeling og valg	Anvendes i flere STL -implementeringer.
Heapsort	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	1	Ingen	Udvælgelse
Indføringssortering	n	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	1	Ja	Indskud	O ( n + d ) , i værste fald over sekvenser, der har d inversioner .
Blok sorter	n	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	1	Ja	Indsætning og sammenlægning	Kombiner en blokbaseret in-place fletningsalgoritme med en sammensmeltning fra bunden opad . ${\ displaystyle O (n)}$
Timsort	n	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	n	Ja	Indsætning og sammenlægning	Gør n-1 sammenligninger, når dataene allerede er sorteret eller omvendt sorteret.
Udvælgelsessort	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	1	Ingen	Udvælgelse	Stabil med ekstra plads, ved brug af sammenkædede lister, eller når den er lavet som en variant af Insertion Sort i stedet for at bytte de to elementer. ${\ displaystyle O (n)}$
Cubesort	n	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	n	Ja	Indskud	Gør n-1 sammenligninger, når dataene allerede er sorteret eller omvendt sorteret.
Shellsort	${\ displaystyle n \ log n}$	${\ displaystyle n^{4/3}}$	${\ displaystyle n^{3/2}}$	1	Ingen	Indskud	Lille kode størrelse.
Boblesort	n	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	1	Ja	Udveksling	Lille kodestørrelse.
Udveksling sorter	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	1	Ja	Udveksling	Lille kodestørrelse.
Træsort	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$(afbalanceret)	n	Ja	Indskud	Ved brug af et selvbalancerende binært søgetræ .
Cyklus sortering	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	1	Ingen	Udvælgelse	På plads med teoretisk optimalt antal skriverier.
Bibliotek sortering	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle n^{2}}$	n	Ingen	Indskud	Ligner en gapped indsættelsessort. Det kræver tilfældigt at permutere input for at garantere med høj sandsynlighed for tidsgrænser, hvilket gør det ikke stabilt.
Tålmodighedssortering	n	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	n	Ingen	Indsætning og markering	Finder alle de længst stigende undersekvenser i O ( n log n ) .
Glat sort	n	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	1	Ingen	Udvælgelse	En adaptiv variant af dyngsort baseret på Leonardo -sekvensen frem for en traditionel binær bunke .
Strand sorter	n	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	n	Ja	Udvælgelse
Turneringssort	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	n	Ingen	Udvælgelse	Variation af Heapsort.
Cocktail shaker sort	n	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	1	Ja	Udveksling	En variant af Bubblesort, der omhandler godt med små værdier i slutningen af ​​listen
Kam sorter	${\ displaystyle n \ log n}$	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	1	Ingen	Udveksling	Hurtigere end boblesort i gennemsnit.
Gnome sort	n	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	1	Ja	Udveksling	Lille kodestørrelse.
Mærkelig - lige slags	n	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	1	Ja	Udveksling	Kan let køres på parallelle processorer.

Ikke-sammenligningssorter

Følgende tabel beskriver heltalssorteringsalgoritmer og andre sorteringsalgoritmer, der ikke er sammenligningssorter . Som sådan er de ikke begrænset til Ω ( n log n ) . Kompleksiteterne nedenfor forudsætter n elementer, der skal sorteres, med nøgler i størrelse k , cifret størrelse d og r antallet af tal, der skal sorteres. Mange af dem er baseret på den antagelse, at nøglestørrelsen er stor nok til, at alle poster har unikke nøgleværdier, og dermed at n ≪ 2 ^k , hvor ≪ betyder "meget mindre end". I enhedsomkostningerne tilfældig adgangsmaskinemodel tager algoritmer med driftstid på f.eks. Radix-sortering stadig tid, der er proportional med Θ ( n log n ) , fordi n er begrænset til ikke at være mere end og et større antal elementer at sortere ville kræve et større k for at gemme dem i hukommelsen. ${\ displaystyle \ scriptstyle n \ cdot {\ frac {k} {d}}}$${\ displaystyle 2^{\ frac {k} {d}}}$

Ikke-sammenligningssorter

Navn	Bedst	Gennemsnit	Værst	Hukommelse	Stabil	n ≪ 2 k	Noter
Pigeonhole sort	-	${\ displaystyle n+2^{k}}$	${\ displaystyle n+2^{k}}$	${\ displaystyle 2^{k}}$	Ja	Ja	Kan ikke sortere ikke-heltal.
Bucket sort (ensartede nøgler)	-	${\ displaystyle n+k}$	${\ displaystyle n^{2} \ cdot k}$	${\ displaystyle n \ cdot k}$	Ja	Ingen	Antager ensartet fordeling af elementer fra domænet i arrayet. Kan heller ikke sortere ikke-heltal
Bucket sort (heltal nøgler)	-	${\ displaystyle n+r}$	${\ displaystyle n+r}$	${\ displaystyle n+r}$	Ja	Ja	Hvis r er , så er den gennemsnitlige tidskompleksitet . ${\ displaystyle O (n)}$${\ displaystyle O (n)}$
Tæller sorter	-	${\ displaystyle n+r}$	${\ displaystyle n+r}$	${\ displaystyle n+r}$	Ja	Ja	Hvis r er , så er den gennemsnitlige tidskompleksitet . ${\ displaystyle O (n)}$${\ displaystyle O (n)}$
LSD Radix Sort	${\ displaystyle n}$	${\ displaystyle n \ cdot {\ frac {k} {d}}}$	${\ displaystyle n \ cdot {\ frac {k} {d}}}$	${\ displaystyle n+2^{d}}$	Ja	Ingen	${\ displaystyle {\ frac {k} {d}}}$rekursionsniveauer, 2 d for tæller array. I modsætning til de fleste distributionstyper kan dette sortere flydende tal , negative tal og mere.
MSD Radix Sort	-	${\ displaystyle n \ cdot {\ frac {k} {d}}}$	${\ displaystyle n \ cdot {\ frac {k} {d}}}$	${\ displaystyle n+2^{d}}$	Ja	Ingen	Stabil version bruger et eksternt array af størrelse n til at rumme alle skraldespandene. Samme som LSD-varianten, den kan sortere ikke-heltal.
MSD Radix Sort (på plads)	-	${\ displaystyle n \ cdot {\ frac {k} {1}}}$	${\ displaystyle n \ cdot {\ frac {k} {1}}}$	${\ displaystyle 2^{1}}$	Ingen	Ingen	d = 1 for in-place, rekursionsniveauer, ingen tæller array. ${\ displaystyle k/1}$
Spredesort	n	${\ displaystyle n \ cdot {\ frac {k} {d}}}$	${\ displaystyle n \ cdot \ left ({{\ frac {k} {s}}+d} \ right)}$	${\ displaystyle {\ frac {k} {d}} \ cdot 2^{d}}$	Ingen	Ingen	Asymptotisk er baseret på antagelsen om, at n ≪ 2 k , men algoritmen kræver ikke dette.
Burstsort	-	${\ displaystyle n \ cdot {\ frac {k} {d}}}$	${\ displaystyle n \ cdot {\ frac {k} {d}}}$	${\ displaystyle n \ cdot {\ frac {k} {d}}}$	Ingen	Ingen	Har bedre konstant faktor end radix sortering til sortering af strenge. Selvom det er lidt afhængigt af specifikationer for almindeligt forekommende strenge.
Flashsort	n	${\ displaystyle n+r}$	${\ displaystyle n^{2}}$	n	Ingen	Ingen	Kræver ensartet distribution af elementer fra domænet i arrayet for at køre i lineær tid. Hvis distributionen er ekstremt skæv, kan den gå kvadratisk, hvis den underliggende sortering er kvadratisk (det er normalt en indsættelsessort). Den lokale version er ikke stabil.
Postbud sort	-	${\ displaystyle n \ cdot {\ frac {k} {d}}}$	${\ displaystyle n \ cdot {\ frac {k} {d}}}$	${\ displaystyle n+2^{d}}$	-	Ingen	En variant af skovlesortering, der fungerer meget på samme måde som MSD Radix Sort. Specifik for post service behov.

Samplingsort kan bruges til at parallelisere enhver af de ikke-sammenligningssorter ved effektivt at distribuere data i flere spande og derefter videresende sortering til flere processorer uden behov for at flette, da spande allerede er sorteret mellem hinanden.

Andre

Nogle algoritmer er langsomme i forhold til dem, der er diskuteret ovenfor, såsom bogosort med ubegrænset løbetid og stooge -sorten, der har O ( n ^2,7 ) driftstid. Disse slags beskrives normalt til uddannelsesmæssige formål for at demonstrere, hvordan algoritmers driftstid estimeres. Følgende tabel beskriver nogle sorteringsalgoritmer, der er upraktiske til brug i virkeligheden i traditionelle softwarekontekster på grund af ekstremt dårlig ydeevne eller specialiserede hardwarekrav.

Navn	Bedst	Gennemsnit	Værst	Hukommelse	Stabil	Sammenligning	Andre noter
Perlesort	n	S	S	${\ displaystyle n^{2}}$	Ikke relevant	Ingen	Fungerer kun med positive heltal. Kræver specialiseret hardware for at den kan køre i garanteret tid. Der er en mulighed for softwareimplementering, men driftstiden vil være , hvor S er summen af ​​alle heltal, der skal sorteres, i tilfælde af små heltal kan det betragtes som lineært. ${\ displaystyle O (n)}$${\ displaystyle O (S)}$
Enkel pandekagesort	-	n	n	${\ displaystyle \ log n}$	Ingen	Ja	Tælling er antallet af vendinger.
Spaghetti (afstemning) sorter	n	n	n	${\ displaystyle n^{2}}$	Ja	Afstemning	Dette er en analog algoritme til lineær tid til sortering af en sekvens af emner, der kræver O ( n ) stakplads, og sorteringen er stabil. Dette kræver n parallelle processorer. Se spaghettisortering#Analyse .
Sorteringsnetværk	Varierer	Varierer	Varierer	Varierer	Varierer (stabile sorteringsnetværk kræver flere sammenligninger)	Ja	Rækkefølgen for sammenligninger er fastsat på forhånd baseret på en fast netværksstørrelse.
Bitonisk sorterer	${\ displaystyle \ log ^{2} n}$ parallel	${\ displaystyle \ log ^{2} n}$ parallel	${\ displaystyle n \ log ^{2} n}$ ikke-parallel	1	Ingen	Ja	En effektiv variation af sorteringsnetværk.
Bogosort	n	${\ displaystyle (n \ gange n!)}$	ubegrænset (bestemt), (forventet)${\ displaystyle (n \ gange n!)}$	1	Ingen	Ja	Tilfældig blanding. Kun brugt til eksempelvis formål, da selv den forventede bedst mulige runtime er forfærdelig.
Stooge sort	${\ displaystyle n^{\ log 3/\ log 1.5}}$	${\ displaystyle n^{\ log 3/\ log 1.5}}$	${\ displaystyle n^{\ log 3/\ log 1.5}}$	n	Ingen	Ja	Langsommere end de fleste sorteringsalgoritmer (også naive) med en tidskompleksitet på O ( n log 3 / log 1.5 ) = O ( n 2.7095 ... ) Kan gøres stabil og er også et sorteringsnetværk .
Langsom sortering	${\ displaystyle n^{\ log n}}$	${\ displaystyle n^{\ log n}}$	${\ displaystyle n^{\ log n}}$	n	Ingen	Ja	En multiplikations- og overgivelsesalgoritme, der er anonym med divider og erobre -algoritme .

Teoretiske computerforskere har detaljerede andre sorteringsalgoritmer, der giver bedre tid end O ( n log n ) tidskompleksitet under forudsætning af yderligere begrænsninger, herunder:

• Thorups algoritme , en randomiseret algoritme til sortering af nøgler fra et domæne med en endelig størrelse, der tager O ( n log log n ) tid og O ( n ) plads.
• En randomiseret heltalssorteringsalgoritme, der tager forventet tid og O ( n ) plads.${\ displaystyle O \ venstre (n {\ sqrt {\ log \ log n}} \ højre)}$

Populære sorteringsalgoritmer

Selvom der er et stort antal sorteringsalgoritmer, dominerer et par algoritmer i praktiske implementeringer. Indsættelsessortering bruges i vid udstrækning til små datasæt, mens der for store datasæt bruges en asymptotisk effektiv sortering, primært heapsort, fletningssort eller quicksort. Effektive implementeringer bruger generelt en hybridalgoritme , der kombinerer en asymptotisk effektiv algoritme til den samlede sortering med indsættelsessortering for små lister i bunden af ​​en rekursion. Højt afstemte implementeringer bruger mere sofistikerede varianter, såsom Timsort (fletningssortering, indsættelsessortering og yderligere logik), der bruges i Android, Java og Python og introsort (kviksort og heapsort), der bruges (i variantformer) i nogle C ++ - sorteringer implementeringer og i .NET.

For mere begrænsede data, f.eks. Tal i et fast interval, anvendes fordelingssorter såsom tællesortering eller radiksortering i vid udstrækning. Boblesort og varianter bruges sjældent i praksis, men findes ofte i undervisning og teoretiske diskussioner.

Ved fysisk sortering af objekter (f.eks. Alfabetiserende papirer, test eller bøger) bruger folk generelt intuitivt indsættelsessorter til små sæt. Ved større sæt gør folk ofte første spand, f.eks. Ved første bogstav, og flere spand gør det muligt at sortere meget store sæt praktisk. Ofte er rummet relativt billigt, f.eks. Ved at sprede genstande ud på gulvet eller over et stort område, men operationer er dyre, især at flytte et objekt en stor afstand - referencelokalitet er vigtig. Fletningssorter er også praktiske for fysiske objekter, især da to hænder kan bruges, en til hver liste til at flette, mens andre algoritmer, såsom heapsort eller quicksort, er dårligt egnede til menneskelig brug. Andre algoritmer, såsom biblioteksortering , en variant af indsættelsessortering, der efterlader mellemrum, er også praktiske til fysisk brug.

Enkle slags

To af de enkleste sorter er indsættelsessortering og udvalgssortering, som begge er effektive på små data på grund af lav overhead, men ikke effektiv på store data. Indsættelsessortering er generelt hurtigere end selektionssort i praksis på grund af færre sammenligninger og god ydeevne på næsten sorterede data, og foretrækkes således i praksis, men udvælgelsessort bruger færre skrivninger og bruges således, når skriveydelse er en begrænsende faktor.

Indføringssortering

Insertion sort er en simpel sorteringsalgoritme, der er relativt effektiv til små lister og for det meste sorterede lister, og bruges ofte som en del af mere sofistikerede algoritmer. Det fungerer ved at tage elementer fra listen en efter en og indsætte dem i deres korrekte position i en ny sorteret liste, der ligner, hvordan vi lægger penge i vores tegnebog. I arrays kan den nye liste og de resterende elementer dele arrayets plads, men indsættelse er dyrt, hvilket kræver at alle følgende elementer skiftes med et. Shellsort (se nedenfor) er en variant af indsættelsessort, der er mere effektiv til større lister.

Udvælgelsessort

Udvælgelsessort er en sammenligningssort på stedet . Det har O ( n ² ) kompleksitet, hvilket gør det ineffektivt på store lister og fungerer generelt dårligere end den tilsvarende indsættelsessort . Udvælgelsessort er kendt for sin enkelhed og har også ydelsesfordele i forhold til mere komplicerede algoritmer i visse situationer.

Algoritmen finder minimumsværdien, bytter den med værdien i den første position og gentager disse trin for resten af ​​listen. Det gør ikke mere end n swaps, og er derfor nyttigt, hvor bytte er meget dyrt.

Effektive sorter

Praktiske generelle sorteringsalgoritmer er næsten altid baseret på en algoritme med gennemsnitlig tidskompleksitet (og generelt værst tænkelig kompleksitet) O ( n log n ), hvoraf de mest almindelige er heapsort, merge sort og quicksort. Hver har fordele og ulemper, hvor den mest betydningsfulde er, at simpel implementering af sammensmeltningssort bruger O ( n ) ekstra plads, og enkel implementering af kviksort har O ( n ² ) værst tænkelige kompleksitet. Disse problemer kan løses eller forbedres på bekostning af en mere kompleks algoritme.

Selvom disse algoritmer er asymptotisk effektive på tilfældige data, bruges der til praktisk effektivitet på virkelige data forskellige modifikationer. For det første bliver omkostningerne til disse algoritmer betydelige for mindre data, så ofte bruges en hybridalgoritme, der normalt skifter til indsættelsessort, når dataene er små nok. For det andet fungerer algoritmerne ofte dårligt på allerede sorterede data eller næsten sorterede data-disse er almindelige i virkelige data og kan sorteres i O ( n ) tid ved passende algoritmer. Endelig kan de også være ustabile , og stabilitet er ofte en ønskelig egenskab af en slags. Således anvendes ofte mere sofistikerede algoritmer, såsom Timsort (baseret på flettesortering ) eller introsort (baseret på kvicksort, der falder tilbage til dyngsort).

Flet sorter

Fletningssort drager fordel af det lette at flette allerede sorterede lister til en ny sorteret liste. Det starter med at sammenligne hvert to element (dvs. 1 med 2, derefter 3 med 4 ...) og bytte dem, hvis det første skulle komme efter det andet. Det fletter derefter hver af de resulterende lister over to til lister med fire, og fletter derefter disse lister med fire osv. indtil endelig to lister er slået sammen til den endelige sorterede liste. Af de algoritmer, der er beskrevet her, er dette den første, der skalerer godt til meget store lister, fordi dens værste tilfælde er O ( n log n ). Det er også let at anvende på lister, ikke kun arrays, da det kun kræver sekventiel adgang, ikke tilfældig adgang. Det har imidlertid yderligere O ( n ) rumkompleksitet og involverer et stort antal kopier i enkle implementeringer.

Merge sort har oplevet en relativt nylig stigning i popularitet for praktiske implementeringer på grund af dets anvendelse i den sofistikerede algoritme Timsort , som bruges til standard sorteringsrutine på programmeringssprogene Python og Java (fra JDK7 ). Selve fletningssortering er standardrutinen i blandt andet Perl og har været brugt i Java mindst siden 2000 i JDK1.3 .

Heapsort

Heapsort er en meget mere effektiv version af udvælgelsessort . Det fungerer også ved at bestemme det største (eller mindste) element på listen, placere det i slutningen (eller begyndelsen) af listen og derefter fortsætte med resten af ​​listen, men udfører denne opgave effektivt ved hjælp af en datastruktur kaldet en bunke , en særlig type binært træ . Når datalisten er blevet til en bunke, er rodnoden garanteret det største (eller mindste) element. Når den fjernes og placeres i slutningen af ​​listen, omarrangeres bunken, så det største resterende element flytter til roden. Ved at bruge bunken tager det O (log n ) tid at finde det næststørste element i stedet for O ( n ) for en lineær scanning som ved simpel markering. Dette gør det muligt for Heapsort at køre i O ( n log n ) tid, og dette er også den værste tilfælde kompleksitet.

Quicksort

Quicksort er en opdelings- og erobringsalgoritme, der er afhængig af en partitionsoperation : for at opdele et array vælges et element kaldet en pivot . Alle elementer, der er mindre end pivoten, flyttes før den, og alle større elementer flyttes efter den. Dette kan gøres effektivt i lineær tid og på stedet . De mindre og større sublister sorteres derefter rekursivt. Dette giver en gennemsnitlig tidskompleks for O ( n log n ) med lav overhead, og derfor er dette en populær algoritme. Effektive implementeringer af quicksort (med in-partitionering) er typisk ustabile sorter og noget komplekse, men er blandt de hurtigste sorteringsalgoritmer i praksis. Sammen med sin beskedne O (log n ) pladsforbrug er quicksort en af ​​de mest populære sorteringsalgoritmer og er tilgængelig på mange standardprogrammeringsbiblioteker.

Den vigtige advarsel om kviksort er, at dens værste ydelse er O ( n ² ); mens dette er sjældent, sker det i naive implementeringer (at vælge det første eller sidste element som pivot) for sorterede data, hvilket er et almindeligt tilfælde. Det mest komplekse problem i quicksort er således at vælge et godt pivot -element, da konsekvent dårlige valg af pivots kan resultere i drastisk langsommere O ( n ² ) ydelse, men godt valg af pivots giver O ( n log n ) ydeevne, hvilket er asymptotisk optimalt . For eksempel, hvis medianen ved hvert trin vælges som pivot, fungerer algoritmen i O ( n  log  n ). At finde medianen, f.eks. Ved medianen af ​​medianer -udvælgelsesalgoritmen, er imidlertid en O ( n ) -operation på usorterede lister og kræver derfor betydelig overhead med sortering. I praksis giver valg af en tilfældig pivot næsten helt sikkert O ( n  log  n ) ydelse.

Shellsort

En Shellsort, forskellig fra boblesort, ved at den flytter elementer til mange byttepositioner .

Shellsort blev opfundet af Donald Shell i 1959. Det forbedres ved indsættelsessortering ved at bevæge sig ud af rækkefølgeelementer mere end én position ad gangen. Konceptet bag Shellsort er, at indsættelsessortering udføres i tide, hvor k er den største afstand mellem to udeplacerede elementer. Det betyder, at de generelt udfører i O ( n ² ), men for data, der for det meste er sorteret, med kun få elementer ude af sted, udfører de hurtigere. Så ved først at sortere elementer langt væk og gradvist reducere kløften mellem elementerne for at sortere, beregner den sidste sortering meget hurtigere. Én implementering kan beskrives som at arrangere datasekvensen i et todimensionelt array og derefter sortere kolonnerne i arrayet ved hjælp af indsættelsessortering. ${\ displaystyle O (kn)}$

Den værst tænkelige tidskompleksitet af Shellsort er et åbent problem og afhænger af den anvendte gap-sekvens med kendte kompleksiteter fra O ( n ² ) til O ( n ^4/3 ) og Θ ( n log ² n ). Dette kombineret med det faktum, at Shellsort er på plads , kun har brug for en relativt lille mængde kode og ikke kræver brug af opkaldsstakken , gør det nyttigt i situationer, hvor hukommelsen er til en overkommelig pris, f.eks. I integrerede systemer og operativsystemkerner .

Boblesort og varianter

Boblesortering og varianter som Shellsort og cocktail sortering er enkle, meget ineffektive sorteringsalgoritmer. De ses ofte i indledende tekster på grund af let analyse, men de bruges sjældent i praksis.

Boblesort

En boblesortering, en sorteringsalgoritme, der løbende går gennem en liste og bytter elementer, indtil de vises i den rigtige rækkefølge.

Boblesortering er en simpel sorteringsalgoritme. Algoritmen starter ved begyndelsen af ​​datasættet. Det sammenligner de to første elementer, og hvis det første er større end det andet, bytter det dem. Det fortsætter med at gøre dette for hvert par tilstødende elementer til slutningen af ​​datasættet. Det starter derefter igen med de to første elementer, gentages, indtil der ikke er sket swaps på den sidste pasning. Denne algoritms gennemsnitlige tid og ydeevne i værste tilfælde er O ( n ² ), så den bruges sjældent til at sortere store, uordnede datasæt. Boblesortering kan bruges til at sortere et lille antal genstande (hvor dets asymptotiske ineffektivitet ikke er en høj straf). Boblesortering kan også bruges effektivt på en liste over enhver længde, der næsten er sorteret (det vil sige, at elementerne ikke er væsentligt malplacerede). For eksempel, hvis et hvilket som helst antal elementer kun er malplaceret med en position (f.eks. 0123546789 og 1032547698), vil boblesorteringsudveksling få dem i orden ved det første pas, og det andet pass vil finde alle elementer i rækkefølge, så sorteringen vil tage kun 2 n tid.

Kam sorter

Comb slags er en forholdsvis enkel sortering algoritme baseret på boblesortering og oprindeligt designet af Włodzimierz Dobosiewicz i 1980. Det blev senere genopdaget og populariseret af Stephen Lacey og Richard boks med en Byte Magazine artikel offentliggjort i april 1991. Den grundlæggende idé er at eliminere skildpadder eller små værdier nær slutningen af ​​listen, da disse i en boble -sortering bremser sorteringen enormt. ( Kaniner , store værdier omkring begyndelsen af ​​listen udgør ikke et problem i boblesortering) Det opnår dette ved i første omgang at bytte elementer, der er en vis afstand fra hinanden i arrayet, frem for kun at bytte elementer, hvis de støder op til hinanden og derefter krympe den valgte afstand, indtil den fungerer som en normal boblesort. Hvis Shellsort således kan betragtes som en generaliseret version af indsættelsessortering, der bytter elementer med en vis afstand fra hinanden, kan kam sorteres som den samme generalisering, der anvendes for boblesortering.

Udveksling sorter

Udvekslingssort forveksles undertiden med boblesortering, selvom algoritmerne faktisk er forskellige. Udvekslingssortering fungerer ved at sammenligne det første element med alle elementer over det, bytte hvor det er nødvendigt og derved garantere, at det første element er korrekt for den endelige sorteringsrækkefølge; det fortsætter derefter med at gøre det samme for det andet element, og så videre. Det mangler den fordel, som boblesortering har ved at detektere i et pass, hvis listen allerede er sorteret, men det kan være hurtigere end boblesortering med en konstant faktor (en færre passerer de data, der skal sorteres; halvt så mange samlede sammenligninger) i værst tænkelige situationer. Ligesom enhver enkel O ( n ² ) sortering kan den være rimelig hurtig over meget små datasæt, selvom indføringssorteringen generelt vil være hurtigere.

Fordeling sorter

Distributionssortering refererer til enhver sorteringsalgoritme, hvor data distribueres fra deres input til flere mellemliggende strukturer, som derefter indsamles og placeres på output. For eksempel, både spand sortere og flashsort er distributions- baseret sortering algoritmer. Distributionssorteringsalgoritmer kan bruges på en enkelt processor, eller de kan være en distribueret algoritme , hvor individuelle undersæt sorteres separat på forskellige processorer og derefter kombineres. Dette tillader ekstern sortering af data for store til at passe ind i en enkelt computers hukommelse.

Tæller sorter

Tællesortering er gældende, når hvert input vides at tilhøre et bestemt sæt, S , af muligheder. Algoritmen kører i O (| S | + n ) tid og O (| S |) hukommelse, hvor n er længden af ​​input. Det fungerer ved at oprette et helt tal array af størrelse | S | og brug af i th bin til at tælle forekomster af det i medlem af S i input. Hver input tælles derefter ved at øge værdien af ​​den tilhørende bakke. Bagefter slås tællearrayet igennem for at arrangere alle input i rækkefølge. Denne sorteringsalgoritme kan ofte ikke bruges, fordi S skal være rimelig lille for, at algoritmen er effektiv, men den er ekstremt hurtig og viser stor asymptotisk adfærd, når n stiger. Det kan også ændres for at give stabil adfærd.

Skovl sort

Bucket sort er en opdelings- og erobringssorteringsalgoritme, der generaliserer tællesortering ved at opdele en matrix i et begrænset antal spande. Hver spand sorteres derefter individuelt, enten ved hjælp af en anden sorteringsalgoritme, eller ved rekursivt at anvende skovlesorteringsalgoritmen.

En bucket -sortering fungerer bedst, når elementerne i datasættet er jævnt fordelt på alle spande.

Radix sorter

Radix -sortering er en algoritme, der sorterer tal ved at behandle individuelle cifre. n tal bestående af k cifre hver er sorteret i O ( n · k ) tid. Radix -sortering kan behandle cifre i hvert tal enten fra det mindst signifikante ciffer (LSD) eller fra det mest signifikante ciffer (MSD). LSD -algoritmen sorterer først listen efter det mindst signifikante ciffer, samtidig med at deres relative rækkefølge bevares ved hjælp af en stabil sortering. Derefter sorterer det dem efter det næste ciffer og så videre fra det mindst betydende til det mest betydningsfulde og ender med en sorteret liste. Selvom LSD radix sortering kræver brug af en stabil sortering, gør MSD radix sorteringsalgoritmen ikke (medmindre der ønskes stabil sortering). MSD radix-sortering på stedet er ikke stabil. Det er almindeligt, at tællesorteringsalgoritmen bruges internt af radix -sorteringen. En hybrid sorteringsmetode, f.eks. Ved at bruge indsættelsessortering til små skraldespande, forbedrer ydelsen af ​​radix -sortering betydeligt.

Hukommelsesbrugsmønstre og indekssortering

Når størrelsen på det array, der skal sorteres, nærmer sig eller overstiger den tilgængelige primære hukommelse, så der skal bruges (meget langsommere) disk- eller swap -plads, bliver hukommelsesforbrugsmønsteret for en sorteringsalgoritme vigtigt, og en algoritme, der muligvis har været rimelig effektiv, når array let passer ind i RAM, kan blive upraktisk. I dette scenario bliver det samlede antal sammenligninger (relativt) mindre vigtigt, og antallet af gange hukommelsessektioner skal kopieres eller byttes til og fra disken kan dominere en algoritmes ydelsesegenskaber. Således kan antallet af passager og lokaliseringen af ​​sammenligninger være vigtigere end det rå antal sammenligninger, da sammenligninger af nærliggende elementer med hinanden sker ved systembushastighed (eller, med caching, selv ved CPU -hastighed), hvilket sammenlignet til diskhastighed, er næsten øjeblikkelig.

For eksempel giver den populære rekursive quicksort -algoritme ganske rimelig ydeevne med tilstrækkelig RAM, men på grund af den rekursive måde, hvorpå den kopierer dele af arrayet, bliver det meget mindre praktisk, når arrayet ikke passer i RAM, fordi det kan forårsage en række langsom kopiering eller flyt operationer til og fra disk. I dette scenario kan en anden algoritme være at foretrække, selvom den kræver flere samlede sammenligninger.

En måde at omgå dette problem, der fungerer godt, når komplekse poster (f.eks. I en relationsdatabase ) bliver sorteret efter et relativt lille nøglefelt, er at oprette et indeks i arrayet og derefter sortere indekset frem for hele array. (En sorteret version af hele arrayet kan derefter produceres med ét pass, læsning fra indekset, men ofte er det unødvendigt, da det har tilstrækkeligt med det sorterede indeks.) Fordi indekset er meget mindre end hele arrayet, kan det evt. passer let i hukommelsen, hvor hele arrayet ikke ville, hvilket effektivt eliminerede disk-swapping-problemet. Denne procedure kaldes undertiden "tagsortering".

En anden teknik til at overvinde hukommelsesstørrelsesproblemet er at bruge ekstern sortering . For eksempel er en af ​​måderne at kombinere to algoritmer på en måde, der udnytter styrken af ​​hver for at forbedre den samlede ydelse. F.eks. Kan arrayet blive opdelt i bidder af en størrelse, der vil passe ind i RAM, indholdet af hver bid del sorteret ved hjælp af en effektiv algoritme (f.eks. Quicksort ), og resultaterne fusioneres ved hjælp af en k -way -fusion, der ligner den, der bruges i flette sorter . Dette er hurtigere end at udføre enten fletningssortering eller kviksort over hele listen.

Teknikker kan også kombineres. Til sortering af meget store datasæt, der langt overstiger systemhukommelsen, skal selv indekset muligvis sorteres ved hjælp af en algoritme eller en kombination af algoritmer, der er designet til at udføre rimeligt med virtuel hukommelse , dvs. for at reducere mængden af ​​udskiftning, der kræves.

Relaterede algoritmer

Relaterede problemer omfatter delvis sortering (sortering kun de k mindste elementer på en liste eller alternativt beregning af de k mindste elementer, men uordnet) og valg (beregning af det k th mindste element). Disse kan løses ineffektivt ved en total sortering, men der findes mere effektive algoritmer, der ofte udledes ved at generalisere en sorteringsalgoritme. Det mest bemærkelsesværdige eksempel er quickselect , der er relateret til quicksort . Omvendt kan nogle sorteringsalgoritmer udledes ved gentagen anvendelse af en selektionsalgoritme; quicksort og quickselect kan ses som det samme svingende træk, der kun adskiller sig i, om man gentager sig på begge sider (quicksort, dividerer og erobrer ) eller den ene side (quickselect, reducerer og erobrer ).

En slags modsætning til en sorteringsalgoritme er en blandet algoritme . Disse er fundamentalt forskellige, fordi de kræver en kilde til tilfældige tal. Blanding kan også implementeres ved en sorteringsalgoritme, nemlig ved en tilfældig sortering: tildeling af et tilfældigt tal til hvert element på listen og derefter sortering baseret på tilfældige tal. Dette gøres dog generelt ikke i praksis, og der er en velkendt enkel og effektiv algoritme til blanding: Fisher – Yates shuffle .

Se også

• Sortering  - Montering af skriftlig information i en standard ordre
• Schwartzian transformation
• Søgealgoritme  - Enhver algoritme, der løser søgeproblemet
• Kvantesortering  - Sorteringsalgoritmer til kvantecomputere

Referencer

Yderligere læsning

• Knuth, Donald E. (1998), Sortering og søgning , The Art of Computer Programming, 3 (2. udgave), Boston: Addison-Wesley, ISBN 0-201-89685-0
• Sedgewick, Robert (1980), "Effektiv sortering efter computer: En introduktion", Computational Probability , New York: Academic Press, s.  101–130 , ISBN 0-12-394680-8

eksterne links

• Sortering af algoritme -animationer på Wayback -maskinen (arkiveret 3. marts 2015).
• Sekventielle og parallelle sorteringsalgoritmer - Forklaringer og analyser af mange sorteringsalgoritmer.
• Ordbog over algoritmer, datastrukturer og problemer - ordbog over algoritmer, teknikker, fælles funktioner og problemer.
• Lidt skeptisk opfattelse af sorteringsalgoritmer - diskuterer flere klassiske algoritmer og fremmer alternativer til quicksort -algoritmen.
• 15 Sorteringsalgoritmer på 6 minutter (Youtube) - Visualisering og "audibilisering" af 15 Sorteringsalgoritmer på 6 minutter.
• A036604 -sekvens i OEIS -databasen med titlen "Sorteringsnumre: minimalt antal sammenligninger, der er nødvendige for at sortere n elementer" - Udført af Ford -Johnson -algoritmen .
• Sorteringsalgoritmer brugt på berømte malerier (Youtube) - Visualisering af sorteringsalgoritmer på mange kendte malerier.
• En sammenligning af sorteringsalgoritmer - Kører en række tests af 9 af de vigtigste sorteringsalgoritmer ved hjælp af Python timeit og Google Colab.