Block sortering

Blocksort (Pocket sort, basket sort, eng. Bucket sort ) - sorteringsalgoritm , där de sorterade elementen är fördelade på ett ändligt antal separata block (fickor, korgar) så att alla element i varje nästa block i ordning alltid är fler (eller mindre ) än i den föregående. Varje block sorteras sedan separat, antingen rekursivt med samma metod eller en annan. Elementen skjuts sedan tillbaka in i arrayen . Denna typ av sortering kan ha en linjär exekveringstid.

Denna algoritm kräver kunskap om vilken typ av data som ska sorteras, utöver funktionerna "jämför" och "byta", tillräckligt för sammanslagningssortering, högsortering, snabbsortering, skalsortering, infogningssortering.

Fördelar: tillhör klassen av snabba algoritmer med linjär O(N) exekveringstid (på bra indata).

Nackdelar: det försämras mycket med ett stort antal lite olika element, eller på den misslyckade funktionen att få korgnumret från innehållet i elementet. I vissa av dessa fall, för strängar som förekommer i implementeringar av BWT- komprimeringsalgoritmen baserad på strängsortering , visar det sig att Sedgwicks snabbsort av strängar är mycket snabbare än blocksorteringshastighet.

Algoritm

Om inmatningselementen är likformigt fördelade är den förväntade körtiden för ficksorteringsalgoritmen linjär. Detta är möjligt på grund av vissa antaganden om indata. Pocketsort förutsätter att indata är jämnt fördelade på intervallet [0, 1) .

Idén med algoritmen är att dela upp segmentet [0, 1) i n identiska segment (fickor) och dela upp n ingångsvärden i dessa fickor. Eftersom de inmatade talen är likformigt fördelade, antas det att varje ficka kommer att falla in i ett litet antal nummer. Sedan sorteras siffrorna i fickorna sekventiellt. En sorterad array erhålls genom att sekventiellt lista elementen i varje ficka.

Pseudokod

funktion bucket-sort(A, n) är hinkar ← ny array med n tomma element för i = 0 till (längd(A)-1) infogar du A [i] i slutet av arrayskoporna[msbits(A[i], k)] för i = 0 till n - 1 do next-sort(hinkar[i]) returnera Array-konkateneringshinkar[0], ..., hinkar[n-1]

Ingången för hink-sorteringsfunktionen är en sorterbar array (lista, samling, etc.) A och antalet block - n .

Buckets- arrayen är en array av arrayer (en array av listor, en array av samlingar, etc.) som matchar naturen hos elementen i A .

Funktionen msbits(x,k) är nära relaterad till antalet block - n (returerar ett värde från 0 till n), och returnerar i allmänhet de k mest signifikanta bitarna från x ( floor(x/2^(storlek ) (x)-k))) ). Olika funktioner kan användas som msbits(x,k) som matchar den sorterade datan och tillåter uppdelning av arrayen A i n block. Till exempel, för AZ-tecken, kan detta vara en matchning med bokstavssiffrorna 0-25, eller returnera koden för den första bokstaven (0-255) för ASCII-teckenuppsättningen; för tal [0, 1) kan det vara funktionsgolvet (n*A[i]) och för en godtycklig uppsättning tal i intervallet [a,b) kan det vara funktionsgolvet (n*(A[i ) ]-a)/(ba)) .

Nästa -sorteringsfunktionen implementerar också en sorteringsalgoritm för varje block som skapas i det första steget. Att rekursivt använda bucket-sort som nästa-sort förvandlar denna algoritm till en radixsortering . I fallet med n = 2 motsvarar det quicksort (om än med ett potentiellt dåligt val av pivot).

Svårighetsgrad

Låt oss uppskatta komplexiteten hos blocksorteringsalgoritmen för det fall då insättningssorteringen används som blocksorteringsalgoritmen ( nästa sortering från pseudokod) .

För att uppskatta algoritmens komplexitet, låt oss introducera en slumpvariabel n i , som anger antalet element som kommer att falla i fickan B[i]. Körtiden för insättningssorteringen är . $O\vänster(n^{2}\höger)$

Körtiden för ficksorteringsalgoritmen är

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

Låt oss beräkna den matematiska förväntan av båda delarna av jämlikheten:

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

Låt oss hitta värdet . $M(n_{i}^{2})$

Låt oss introducera en slumpvariabel , som är lika med 1 om den faller i den i -te fickan, och 0 annars: $X_{{ij}}$ A[j]

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

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

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

Om k ≠ j , X ij och X ik är oberoende, så:

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

På det här sättet

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

Så den förväntade körtiden för ficksorteringsalgoritmen är

$\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 linjär tid // Algoritmer: Konstruktion och analys, 2:a upplagan = Introduktion till algoritmer andra upplagan. - M .: "Williams" , 2005. - S. 230 - 234. - ISBN 5-8459-0857-4 .

Se även

Lista över sorteringsalgoritmer

Länkar

Visualizer1 är en Java-applet.
Visualizer2 är en Java-applet.

Sorteringsalgoritmer
Teori	Komplexitet O notation Orderförhållande Sorteringstyper hållbar Inre Extern
Utbyta	bubbla Omrörning Dvärgar Snabb Hårkam Sortering jämnt-udda Bitvis
Val	Val Pyramidformad Slät
Insatser	Insatser shella träd
fusion	fusion
Inga jämförelser	Räkning blockera
hybrid	introsort Timsort
Övrig	Topologiska nätverk biton
opraktisk	Bogosort Stooge sort pannkaka långsam