Sorteringsalgoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 8. marts 2020; verifikation kræver 41 redigeringer .

En sorteringsalgoritme er en algoritme til at bestille elementer i et array. I det tilfælde, hvor et element i et array har flere felter, kaldes det felt, der fungerer som rækkefølgekriteriet, sorteringsnøglen. I praksis fungerer et tal ofte som en nøgle, og de resterende felter gemmer nogle data, som ikke påvirker algoritmens funktion.

Historie

De første prototyper af moderne sorteringsmetoder dukkede op allerede i det 19. århundrede. I 1890, for at fremskynde behandlingen af amerikanske folketællingsdata , skabte amerikaneren Herman Hollerith den første statistiske tabulator , en elektromekanisk maskine designet til automatisk at behandle information registreret på hulkort [1] . Holleriths maskine havde en særlig "sorteringskasse" med 26 indvendige rum. Når man arbejdede med maskinen, skulle operatøren indsætte et hulkort og sænke håndtaget. Takket være hullerne på hulkortet blev et bestemt elektrisk kredsløb lukket , og indikationen af skiven forbundet med det steg med én. Samtidig blev et af sorteringsboksens 26 låg åbnet, og et hulkort blev flyttet til det tilsvarende rum, hvorefter låget blev lukket. Denne maskine gjorde det muligt at behandle omkring 50 kort i minuttet, hvilket accelererede databehandlingen med 3 gange. Til folketællingen i 1900 forbedrede Hollerith maskinen ved at automatisere indføringen af kort [1] . Driften af Holleriths sorteringsmaskine var baseret på radix-sorteringsmetoder . Maskinpatentet angiver sortering "individuelt for hver kolonne", men angiver ikke rækkefølgen. En anden lignende maskine, patenteret i 1894 af John Gore, nævner sortering fra tiere kolonnen [2] . Sorteringsmetoden, der starter med kolonnen enhed, dukker først op i litteraturen i slutningen af 1930'erne [3] . På dette tidspunkt har sorteringsmaskiner allerede gjort det muligt at behandle op til 400 kort i minuttet [4] .

I fremtiden viste historien om algoritmer sig at være forbundet med udviklingen af elektroniske computere . Ifølge nogle kilder var det sorteringsprogrammet, der blev det første program til computere. Nogle computerdesignere, især udviklerne af EDVAC , kaldte problemet med datasortering for den mest typiske ikke-numeriske opgave for computere. I 1945 udviklede John von Neumann flettesorteringsprogrammer for at teste en række kommandoer til EDVAC . Samme år udviklede den tyske ingeniør Konrad Zuse et program til simpel indstikssortering . På dette tidspunkt var der allerede dukket hurtige specialiserede sorteringsmaskiner op, i sammenligning med hvilke effektiviteten af de udviklede computere blev evalueret [4] . Den første publicerede diskussion om computerassisteret sortering var et foredrag af John Mauchly i 1946. Mauchly viste, at sortering også kunne være nyttig til numeriske beregninger, beskrev simple indsættelses- og binære indsættelsessorteringsmetoder og radix-sortering med partielle gennemløb. Senere grundlagde han Eckert-Mauchly Computer Corporation sammen med ingeniør John Eckert for at producere nogle af de tidligste BINAC og UNIVAC elektroniske computere [5] . Sammen med de bemærkede interne sorteringsalgoritmer dukkede eksterne sorteringsalgoritmer op , hvis udvikling blev lettet af den begrænsede mængde hukommelse på de første computere [4] . Især er metoderne til balanceret to-vejs bitvis sortering og balanceret to-vejs sammenlægning [5] blevet foreslået .

I 1952 var mange interne sorteringsmetoder allerede i praksis, men teorien var relativt dårligt udviklet [6] . I oktober 1952 leverede Daniel Goldenberg fem sorteringsmetoder med en best case og worst case analyse for hver. I 1954 udviklede Harold Seward Goldenbergs ideer og analyserede også eksterne sorteringsmetoder. Howard Demuth i 1956 overvejede tre abstrakte modeller af sorteringsproblemet: Brug af cirkulær hukommelse, lineær hukommelse og random access memory. For hvert af disse problemer foreslog forfatteren optimale eller næsten optimale sorteringsmetoder, som hjalp med at forbinde teori med praksis [7] . På grund af det lille antal personer, der er forbundet med computerteknologi, optrådte disse rapporter ikke i den "åbne litteratur". Den første store oversigtsartikel om sortering, som udkom på tryk i 1955, var J. Hoskens værk, hvor han beskrev alt det specialudstyr og sorteringsmetoder til computere, der var til rådighed på det tidspunkt, baseret på fabrikanternes brochurer. I 1956 analyserede E. Friend i sit arbejde de matematiske egenskaber af et stort antal interne og eksterne sorteringsalgoritmer og foreslog nogle nye metoder [8] .

Siden da er mange forskellige sorteringsalgoritmer blevet foreslået: for eksempel beregning af en adresse i 1956; sammensmeltning med indsættelse, udveksling radixsort , kaskadefletning og Shells metode i 1959, flerfaset sammensmeltning og træindsættelser i 1960, oscillerende sortering og Hoares kviksortering i 1962, Williams' heapsort og byttesort med Batchers sammensmeltning i 1964. I slutningen af 60'erne skete der også en intensiv udvikling af teorien om sortering [9] . Algoritmerne, der dukkede op senere, var i mange henseender variationer af allerede kendte metoder. Adaptive sorteringsmetoder er blevet udbredt, fokuseret på hurtigere eksekvering i tilfælde, hvor inputsekvensen opfylder forudbestemte kriterier [9] .

Problemformulering

nøglen , der styrer sorteringsprocessen. På nøglesættet er ordensrelationen "<" defineret, således at følgende betingelser er opfyldt for alle tre nøgleværdier [10] : $K_{j}$ $a,b,c$

lov om trikotomi : enten, eller, eller; $a<b$ $a>b$ $a=b$
transitivitetslov : hvis og , så . $a<b$ $b<c$ $a<c$

Disse betingelser definerer det matematiske koncept for en lineær eller perfekt rækkefølge, og sæt, der opfylder dem, kan sorteres ved de fleste metoder [10] .

Opgaven med at sortere er at finde en sådan permutation af poster med indekser , hvorefter nøglerne vil blive placeret i ikke-faldende rækkefølge [10] : $p(1)p(2)\dots p(n)$ $\{1,2,\dots ,N\}$

{\displaystyle K_{p(1)}\leqslant K_{p(2)}\leqslant \dots \leqslant K_{p(n)))

Sortering kaldes stabil , hvis den ikke ændrer den relative position af elementer med de samme taster [10] :

p(i)<p(j)

for enhver og .

{\displaystyle K_{p(i)}=K_{p(j)))

i<j

Sorteringsmetoder kan opdeles i interne og eksterne . Intern sortering bruges til data, der passer i RAM, hvilket gør det mere fleksibelt i forhold til datastrukturer. Ved ekstern sortering placeres data ikke i RAM, og det er fokuseret på at opnå resultater under forhold med begrænsede ressourcer [11] .

Sorteringsalgoritmevurdering

Sorteringsalgoritmer er vurderet til udførelseshastighed og hukommelseseffektivitet:

Tid er hovedparameteren, der karakteriserer algoritmens hastighed. Kaldes også beregningsmæssig kompleksitet . For bestilling er den dårligste , gennemsnitlige og bedste opførsel af algoritmen med hensyn til kardinalitet af inputsættet A vigtig . Hvis input til algoritmen er sat A , så betegner vi n = | A |. For en typisk algoritme er god opførsel O ( n log n ) og dårlig opførsel er O ( n 2 ) . Den ideelle adfærd til at bestille er O ( n ) . Sorteringsalgoritmer, der kun bruger den abstrakte nøglesammenligningsoperation, har altid brug for mindst sammenligninger. Der er dog en O ( n log log n ) sorteringsalgoritme af Yijie Han , der udnytter det faktum, at nøglerummet er begrænset (det er ekstremt komplekst, og O- notationen skjuler en meget stor koefficient, hvilket gør det umuligt at anvende i hverdagspraksis) [12] . Der er også konceptet med sorteringsnetværk . Hvis det antages, at det er muligt at udføre flere sammenligninger på samme tid (f.eks. i parallel beregning ), er det muligt at sortere n tal i O (log 2 n ) operationer. I dette tilfælde skal tallet n være kendt på forhånd;
Hukommelse - en række algoritmer kræver tildeling af yderligere hukommelse til midlertidig datalagring. Typisk kræver disse algoritmer O (log n ) hukommelse. Evalueringen tager ikke højde for den plads, som det oprindelige array optager, og omkostningerne uafhængigt af inputsekvensen, for eksempel til lagring af programkoden (da alt dette forbruger O (1) ). Sorteringsalgoritmer, der ikke bruger yderligere hukommelse, omtales som in-place sorteringer .

O ( n log n ) optimalitet generelt

I det generelle tilfælde antager sorteringsproblemet, at den eneste nødvendige operation på elementer er en sammenligning. Svaret til at sammenligne elementer og kan være en af to muligheder: eller . Derfor, hvis algoritmen i løbet af arbejdet foretager sammenligninger, er der kun mulige kombinationer af svar på dem. $-en$ $b$ $a\leq b$ $a>b$ $k$ $2^k$

Antallet af permutationer af elementerne er . For surjektivt at kunne kortlægge mængden af kombinationer af svar til mængden af alle permutationer, skal antallet af sammenligninger være mindst (fordi sammenligning er den eneste tilladte operation). $n$ $n!$ $\log _{2}{n!}$

Tager vi logaritmen af Stirling-formlen , kan vi finde ud af, at [13] $\log _{2}{n!}=\log _{2}{\left({\sqrt {2\pi n}}\left({\frac {n}{e}}\right) ^{n}\right)}=n\log n+O(n)=\Omega (n\log n)$

Egenskaber og typer

Stabilitetsstabil sortering ændrer ikke den relative position af elementer med de samme nøgler [ 14] .
Naturlighed af adfærd - effektiviteten af metoden ved behandling af allerede bestilte eller delvist bestilte data. Algoritmen opfører sig naturligt, hvis den tager højde for denne egenskab ved inputsekvensen og yder bedre.
Brug af sammenligningsoperationen. Algoritmer, der bruger sammenligninger mellem elementer til at sortere, kaldes sammenligningsbaserede. Den mindste worst-case kompleksitet for disse algoritmer er ( ), men de adskiller sig i applikationsfleksibilitet. Til særlige tilfælde (datatyper) er der mere effektive algoritmer. $O$ $n\cdot\log n$

En anden vigtig egenskab ved algoritmen er dens omfang. Der er to hovedtyper af bestilling:

Intern sortering fungerer på arrays, der passer helt ind i RAM med tilfældig adgang til enhver celle. Data bestilles normalt samme sted uden ekstra omkostninger.
- Hukommelsessøgning og cachelagring er meget udbredt i moderne pc-arkitekturer . Sorteringsalgoritmen burde fungere godt sammen med de anvendte cache- og byttealgoritmer.
Ekstern sortering fungerer på store lagerenheder, men ikke med tilfældig adgang, men sekventiel (filbestilling), det vil sige i øjeblikket er kun ét element "synligt", og omkostningerne ved tilbagespoling er urimeligt høje sammenlignet med hukommelse. Dette pålægger nogle yderligere begrænsninger for algoritmen og fører til specielle bestillingsmetoder, der normalt bruger ekstra diskplads. Derudover er adgang til data i ekstern hukommelse meget langsommere end operationer med RAM.
- Adgang til mediet udføres på en sekventiel måde: på hvert tidspunkt kan kun det element, der følger det aktuelle, læses eller skrives.
- Mængden af data tillader dem ikke at passe i RAM.

Algoritmer er også klassificeret efter:

behovet for yderligere hukommelse eller dets fravær
behovet for viden om strukturen af data, der går ud over sammenligningsoperationen, eller manglen på det

En oversigt over de mest populære sorteringsalgoritmer

Algoritme	Beskrivelse	Tidspunkt for færdiggørelse		Hukommelsesomkostninger	Bemærk
Algoritme	Beskrivelse	I værste fald	Gennemsnit	Bedste scenario	Bemærk
Vedvarende sorteringsalgoritmer
Boble sortering _ _ _	Itererer gennem arrayet, sammenligner på hinanden følgende par af elementer og bytter dem, hvis de er i den forkerte rækkefølge.	$O(n^{2})$	$O(n^{2})$	$O(1)$	I processen med sortering "dukker minimumselementet op" i toppen af arrayet, der ligner en boble
Blandingssort ( eng. Cocktailsort )	Tovejs, optimeret boblesortering	$O(n^{2})$	$O(n^{2})$	$O(1)$
Indsættelsessort _ _ _ _	Elementerne i inputsekvensen undersøges et ad gangen, og hvert nyt element placeres et passende sted blandt de tidligere bestilte elementer.	$O(n^{2})$	$O(n^{2})$	$O(1)$
Gnome sortering ( eng. Gnome sort )	En hybrid af indsættelse og boblesorter .	$O(n^{2})$	$O(n^{2})$	$O(1)$	Navnet kommer fra havenissernes formodede adfærd, når de sorterer en række havekrukker.
Flet sortering _ _ _	Sorterer rekursivt halvdelene af en matrix og kombinerer dem derefter til én	$O(n\log {n})$	$O(n\log {n})$	$På)$
Sortering ved hjælp af et binært træ ( eng. Tree sort )	Baseret på de indledende data opbygges et binært søgetræ , hvor minimumsværdierne samles sekventielt	$O(n^{2})$	$O(n\log {n})$	$På)$
Sortering af Timsort _ _ _ _	En hybrid af indsættelsessortering og flettesortering . Baseret på den antagelse, at når man løser praktiske problemer, består input-arrayet ofte af sorterede subarrays	$O(n\log {n})$	$O(n\log {n})$	$O(1)$
Ustabile sorteringsalgoritmer
Udvælgelsessortering _ _ _ _	Opdeler input-arrayet i ordnede og uordnede dele. Overfører derefter sekventielt de mindste elementer fra den anden til den første del.	$O(n^{2})$	$O(n^{2})$	$O(1)$
Kam sortering _ _ _	En modifikation af boblesortering , hvor afstanden mellem sammenlignede værdipar er anderledes end 1	$O(n^{2})$	$O(n^{2}/2^{p})$	$O(1)$	På trods af den større algoritmiske kompleksitet vil kamsortering være mere effektiv end hurtig sortering for ikke særlig store matrixstørrelser.
Skalsortering _ _ _ _	En modifikation af indsættelsessort , hvor afstanden mellem sammenlignede værdipar er anderledes end 1	$O(n^{2})$	$O(n\log ^{2}{n})$	$O(1)$
Dyngesortering (dyngesortering, Dyngesortering)	Baseret på de indledende data bygges en binær heap , hvor minimumsværdierne samles sekventielt	$O(n\log {n})$	$O(n\log {n})$	$På)$
Smoothsort _ _ _ _	Ændring af heapsort , optimering af sortering af et delvist ordnet array	$O(n\log {n})$	$O(n\log {n})$	$På)$
Quicksort _ _ _ _	Referenceelementet p er valgt. Alle taster mindre end p flyttes til venstre for den, og alle taster større end eller lig med p flyttes til højre. Dernæst anvendes algoritmen rekursivt på hver af delene	$O(n^{2})$	$O(n\log {n})$	$O(1)$
Introspektiv sortering _ _ _	Hybrid af hurtig og heapsort	$O(n\log {n})$	$O(n\log {n})$	$På)$
Dumme sortering ( eng. Stooge sort )	Bytter om nødvendigt det første og det sidste element i et array. Det opdeler derefter arrayet i tre dele, som hver kører rekursivt	$O(n^{\log {3}/\log {1.5)))$ $=O(n^{2.709...})$	$O(n^{2.709...})$	$O(1)$	Metoden er opkaldt efter den amerikanske komikergruppe Three Stooges . Ligheden ligger i, at algoritmen suser vanvittigt hen over de allerede sorterede tredjedele af arrayet.
Upraktiske sorteringsalgoritmer
Bogosort	Arrayet blandes tilfældigt, indtil det er sorteret.	Ubegrænset	$O(n!)$	$O(1)$	Anvendes kun til akademiske formål
Sorter efter permutation	Alle mulige array-sekvenser genereres, hvorfra en ordnet sekvens vælges.	$O(n!)$	$O(n!)$	$På)$	Anvendes kun til akademiske formål
Gravity sort ( engelsk perle sortering )	Tal er repræsenteret som perler på stifter, derefter sorteret efter tyngdekraft	$O(\sqrt{n})$	$O(\sqrt{n})$	$O(n^{2})$	Kræver specialiseret hardware
Algoritmer er ikke baseret på sammenligninger
Bloker sortering _ _ _	Elementer er fordelt i blokke i henhold til en række værdier, som hver derefter sorteres rekursivt	$O(n^{2})$	$O(n^{2}+n/k+k)$	$O(n+k)$	$k$ - et forudbestemt antal kurve
Bitwise sort ( eng. Radix sort )	Arrayet er sorteret efter ved hjælp af en bitvis sammenligning af tal	$O(wn)$	$O(wn)$	$På)$	$w$ er antallet af bits, der kræves for at gemme hver nøgle.
Tællesort _ _ _ _	Antallet af forekomster af hvert heltal fra rækken af nøgler i arrayet tælles. Derefter udskrives værdierne for alle ikke-nul-værdier	$O(n+k)$	$O(n+k)$	$O(n+k)$	$k$ - maksimal værdi af nøgleelementer

Sortering af strenge

En almindelig anvendelse af sorteringsalgoritmer er strengsortering. En generaliseret algoritme kan se sådan ud: først sorteres et sæt strenge efter det første tegn i hver streng, derefter sorteres hvert undersæt af strenge, der har det samme første tegn, efter det andet tegn, og så videre, indtil alle strenge er sorteret . I dette tilfælde anses det manglende tegn (når man sammenligner en streng med længde N med en streng med længde N + 1) som mindre end ethvert tegn.

Anvendelse af denne metode på strenge, der er tal i naturlig notation, giver kontraintuitive resultater: for eksempel er "9" større end "11", fordi det første tegn i den første streng har en større værdi end det første tegn i den anden. For at løse dette problem kan sorteringsalgoritmen konvertere strengene, der sorteres, til tal og sortere dem som tal. En sådan algoritme kaldes "numerisk sortering", og den tidligere beskrevne kaldes "strengsortering". Også i praksis er en effektiv måde at løse problemet med at sortere strenge, der indeholder tal, ved at tilføje et vist antal nuller foran tallet, så "011" vil blive betragtet som større end "009".

Se også

Noter

↑ 1 2 Knuth, 2007 , s. 416.
↑ Knuth, 2007 , s. 417.
↑ Knuth, 2007 , s. 417-418.
↑ 1 2 3 Knut, 2007 , s. 418.
↑ 1 2 Knuth, 2007 , s. 419.
↑ Knuth, 2007 , s. 420.
↑ Knuth, 2007 , s. 420-421.
↑ Knuth, 2007 , s. 421.
↑ 1 2 Knuth, 2007 , s. 422.
↑ 1 2 3 4 Knut, 2007 , s. 22.
↑ Knuth, 2007 , s. 23.
↑ Han, Yijie. Deterministisk sortering i O(n log log n) tid og lineært rum // Journal of Algorithms. Kognition, informatik og logik. - 2004. - T. 50 , nr. 1 . - S. 96-105 . - doi : 10.1016/j.jalgor.2003.09.001 .
↑ Donald Knuth. 5.3.1. Sortering med et minimum antal sammenligninger // The Art of Programming. - 2. - Williams, 2002.
↑ Knuth, 2007 .

Litteratur

Knut D. E. Kunsten at programmere. Bind 3. Sortering og søgning = The Art of Computer Programming. Bind 3. Sortering og søgning / red. V. T. Tertyshny (kap. 5) og I. V. Krasikov (kap. 6). - 2. udg. - Moskva: Williams, 2007. - T. 3. - 832 s. — ISBN 5-8459-0082-1 .
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmer: konstruktion og analyse = INTRODUKTION TIL ALGORITHMER. - 2. udg. - M .: "Williams" , 2006. - S. 1296. - ISBN 5-8459-0857-4 .
Robert Sedgwick. Fundamentale algoritmer i C. Fundamentals/Datastrukturer/Sortering/Søgning. - Sankt Petersborg. : DiaSoftYUP, 2003. - S. 672. - ISBN 5-93772-081-4 .
Magnus Lie Hetland. Python-algoritmer: Mestring af grundlæggende algoritmer i Python-sproget. - Apress, 2010. - 336 s. - ISBN 978-1-4302-3237-7 .

Links

Teori, opgaver, testsystem
Sorteringsalgoritmer på algolist.manual.ru
Animeret sammenligning af sorteringsalgoritmer

Sorteringsalgoritmer
Teori	Kompleksitet O notation Ordreforhold Sorter typer bæredygtige Indre Ekstern
Udveksling	boble Omrøring Dværge Hurtig Kam Sortering lige-ulige Bitvis
Valg	Valg Pyramideformet Glat
indsætter	indsætter shella træ
fusion	fusion
Ingen sammenligninger	Tæller blok
hybrid	introsort Timsort
Andet	Topologisk netværk biton
upraktisk	Bogosort Stooge sort pandekage langsom