Blok sortering

Bloksortering (Pocket sort, basket sort, eng. Bucket sort ) - sorteringsalgoritme , hvor de sorterede elementer er fordelt på et endeligt antal separate blokke (lommer, kurve), således at alle elementer i hver næste blok i rækkefølge altid er flere (eller mindre ) end i den foregående. Hver blok sorteres derefter separat, enten rekursivt ved den samme metode eller en anden. Elementerne skubbes derefter tilbage i arrayet . Denne type sortering kan have en lineær udførelsestid.

Denne algoritme kræver viden om arten af de data, der skal sorteres, ud over funktionerne "sammenlign" og "swap", tilstrækkeligt til flettesortering, heapsortering, hurtig sortering, shellsortering, indsættelsessortering.

Fordele: tilhører klassen af hurtige algoritmer med lineær O(N) eksekveringstid (på gode inputdata).

Ulemper: det nedbrydes meget med et stort antal små forskellige elementer, eller på den mislykkede funktion at få kurvnummeret fra indholdet af elementet. I nogle af disse tilfælde, for strenge, der forekommer i implementeringer af BWT -komprimeringsalgoritmen baseret på strengsortering , viser det sig, at Sedgwicks quicksort af strenge er meget hurtigere end blocksort i hastighed.

Algoritme

Hvis input-elementerne er ensartet fordelt , så er den forventede køretid for lommesorteringsalgoritmen lineær. Dette er muligt på grund af visse antagelser om inputdata. Pocketsort antager, at inputdataene er jævnt fordelt på segmentet [0, 1) .

Ideen med algoritmen er at opdele segmentet [0, 1) i n identiske segmenter (lommer) og opdele n inputværdier i disse lommer. Da inputtallene er ensartet fordelt, antages det, at hver lomme vil falde ind i et lille antal tal. Derefter sorteres tallene i lommerne sekventielt. Et sorteret array opnås ved sekventielt at liste elementerne i hver lomme.

Pseudokode

funktion bucket-sort(A, n) er buckets ← ny matrix af n tomme elementer for i = 0 til (længde(A)-1) , indsæt A[i] i slutningen af array-buckets[msbits(A[i], k)] for i = 0 til n - 1 do next-sort(buckets[i]) returner Array-sammenkædning buckets[0], ..., buckets[n-1]

Indgangen til bucket-sort- funktionen er en sorterbar matrix (liste, samling osv.) A og antallet af blokke - n .

Buckets -arrayet er et array af arrays (en matrix af lister, en matrix af samlinger osv.), der matcher arten af elementerne i A .

Funktionen msbits(x,k) er tæt forbundet med antallet af blokke - n (returnerer en værdi fra 0 til n), og returnerer generelt de k mest signifikante bits fra x ( floor(x/2^(størrelse) (x)-k))) ). Forskellige funktioner kan bruges som msbits(x,k) , der matcher arten af de sorterede data og tillader opdeling af array A i n blokke. For AZ-tegn kan dette f.eks. være et match med bogstaverne 0-25 eller returnere koden for det første bogstav (0-255) for ASCII-tegnsættet; for tal [0, 1) kan det være funktionsgulvet (n*A[i]) , og for et vilkårligt sæt tal i intervallet [a,b) kan det være funktionsgulvet (n*(A[i) ]-a)/(ba)) .

Næste -sorteringsfunktionen implementerer også en sorteringsalgoritme for hver blok, der er oprettet i det første trin. Rekursiv brug af bucket-sort som næste-sort gør denne algoritme til en radix-sortering . I tilfælde af n = 2 svarer det til quicksort (omend med et potentielt dårligt valg af pivot).

Sværhedsgrad

Lad os estimere kompleksiteten af bloksorteringsalgoritmen for det tilfælde, hvor indsættelsessortering bruges som bloksorteringsalgoritmen ( næste sortering fra pseudokode) .

For at estimere kompleksiteten af algoritmen, lad os introducere en tilfældig variabel n i , der angiver antallet af elementer, der vil falde i lommen B[i]. Køretiden for indsættelsessortering er . $O\venstre(n^{2}\højre)$

Løbetiden for lommesorteringsalgoritmen er

$T(n)=\Theta (n)+\sum _{{i=0}}^{{n-1}}O(n_{i}^{2})$

Lad os beregne den matematiske forventning for begge dele af ligheden:

$M\left(T(n)\right)=M\left(\Theta (n)+\sum _{{i=0}}^{{n-1}}O(n_{i}^{2} )\right)=\Theta (n)+\sum _{{i=0}}^{{n-1}}O\venstre(M(n_{i}^{2})\right)$

Lad os finde værdien . $M(n_{i}^{2})$

Lad os introducere en tilfældig variabel , som er lig med 1 , hvis den falder i den i -te lomme, og 0 ellers: $X_{{ij}}$ A[j]

$n_{i}=\sum _{{j=1}}^{n}X_{{ij}}$

${\begin{matrix}M\left(n_{i}^{2}\right)=&M\left[\left(\sum _{{j=1}}^{n}X_{{ij}}\ højre)^{2}\right]=M\venstre[\sum _{{j=1}}^{n}\sum _{{k=1}}^{n}X_{{ij}}X_{ {ik}}\right]=\\\ &\sum _{{j=1}}^{n}M\venstre[X_{{ij}}^{2}\right]+\sum _{{1 \leq j\leq n}}\ \sum _{{1\leq k\leq n,k\neq j}}M\venstre[X_{{ij}}X_{{ik}}\right]\end{ matrix}}$

$M\venstre[X_{{ij}}^{2}\right]=1\cdot {\frac {1}{n}}+0\cdot \left(1-{\frac {1}{n}} \right)={\frac {1}{n}}$

Hvis k ≠ j , X ij og X ik er uafhængige, så:

$M\venstre[X_{{ij}}X_{{ik}}\right]=M\left[X_{{ij}}\right]M\left[X_{{ik}}\right]={\frac {1}{n^{2}}}$

På denne måde

$M\left(n_{i}^{2}\right)=\sum _{{j=1}}^{{n}}{\frac {1}{n}}+\sum _{{1\ leq j\leq n}}\ \sum _{{1\leq k\leq n,k\neq j}}{\frac {1}{n^{2}}}=2-{\frac {1} {n}}$

Så den forventede køretid for lommesorteringsalgoritmen er

$\Theta (n)+n\cdot O(2-1/n)=\Theta (n)$

Litteratur

Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Kapitel 8 Sortering i lineær tid // Algoritmer: Konstruktion og analyse, 2. udgave = Introduktion til algoritmer anden udgave. - M .: "Williams" , 2005. - S. 230 - 234. - ISBN 5-8459-0857-4 .

Se også

Liste over sorteringsalgoritmer

Links

Visualizer1 er en Java-applet.
Visualizer2 er en Java-applet.

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