Blokové řazení

Třídění bloků (Pocket sort, basket sort, angl. Bucket sort ) - třídící algoritmus , ve kterém jsou setříděné prvky rozděleny mezi konečný počet samostatných bloků (kapsy, košíky) tak, aby všech prvků v každém dalším bloku v pořadí bylo vždy více (nebo méně) než v předchozím. Každý blok se pak třídí samostatně, buď rekurzivně stejnou nebo jinou metodou. Prvky jsou poté zatlačeny zpět do pole . Tento typ řazení může mít lineární dobu provádění.

Tento algoritmus vyžaduje znalosti o povaze dat, která mají být tříděna, kromě funkcí „porovnat“ a „swap“, což je dostatečné pro třídění sloučení, třídění haldy, rychlé třídění, třídění shellu, třídění vkládání.

Výhody: patří do třídy rychlých algoritmů s lineární dobou provádění O(N) (při dobrých vstupních datech).

Nevýhody: hodně degraduje velkým množstvím málo odlišných prvků, nebo na neúspěšné funkci získání čísla košíku z obsahu prvku. V některých z těchto případů se u řetězců, které se vyskytují v implementacích kompresního algoritmu BWT založeného na třídění řetězců , ukazuje, že rychlé třídění řetězců v Sedgwicku je z hlediska rychlosti mnohem rychlejší než blockort .

Algoritmus

Pokud jsou vstupní prvky rovnoměrně rozloženy , pak je očekávaná doba běhu algoritmu třídění kapes lineární. To je možné díky určitým předpokladům o vstupních datech. Pocketsort předpokládá, že vstupní data jsou rovnoměrně rozložena na intervalu [0, 1) .

Myšlenkou algoritmu je rozdělit segment [0, 1) na n identických segmentů (kapes) a do těchto kapes rozdělit n vstupních hodnot. Protože jsou vstupní čísla rovnoměrně rozdělena, předpokládá se, že každá kapsa bude spadat do malého počtu čísel. Potom se čísla v kapsách postupně třídí. Seřazené pole se získá postupným výpisem prvků každé kapsy.

Pseudokód

funkce bucket-sort(A, n) je buckets ← nové pole n prázdných prvků for i = 0 to (length(A)-1) do vložte A[i] na konec pole buckets[msbits(A[i], k)] pro i = 0 to n - 1 do další řazení (kbelíky[i]) return pole zřetězení buckets[0], ..., buckets[n-1]

Vstupem funkce bucket-sort je tříditelné pole (seznam, kolekce atd.) A a počet bloků - n .

Pole buckets je pole polí (pole seznamů, pole kolekcí atd.), které odpovídají povaze prvků A .

Funkce msbits(x,k) úzce souvisí s počtem bloků - n (vrací hodnotu od 0 do n) a obecně vrací k nejvýznamnějších bitů z x ( patro(x/2^(velikost (x)-k))) ). Jako msbits(x,k) lze použít různé funkce , které odpovídají povaze setříděných dat a umožňují rozdělení pole A na n bloků. Například pro znaky AZ to může být shoda s čísly písmen 0-25 nebo vrátit kód prvního písmene (0-255) znakové sady ASCII; pro čísla [0, 1) to může být funkční patro(n*A[i]) a pro libovolnou množinu čísel v intervalu [a,b) to může být funkční patro (n*(A[i ]-a)/(ba)) .

Funkce dalšího třídění také implementuje třídicí algoritmus pro každý blok vytvořený v prvním kroku. Rekurzivní použití bucket-sort jako dalšího řazení změní tento algoritmus na radixové řazení . V případě n = 2 odpovídá quicksortu (i když s potenciálně špatnou volbou pivotu).

Hodnocení obtížnosti

Odhadněme složitost algoritmu třídění bloků pro případ, kdy je jako algoritmus třídění bloků použito řazení vkládání ( další řazení z pseudokódu) .

Abychom odhadli složitost algoritmu, zaveďme náhodnou veličinu n i , označující počet prvků, které spadnou do kapsy B[i]. Průběžná doba řazení vložení je . $O\left(n^{2}\vpravo)$

Doba běhu algoritmu řazení v kapse je

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

Vypočítejme matematické očekávání obou částí rovnosti:

$M\left(T(n)\vpravo)=M\left(\Theta (n)+\součet _{{i=0}}^{{n-1}}O(n_{i}^{2} )\vpravo)=\Theta (n)+\součet _{{i=0}}^{{n-1}}O\levý(M(n_{i}^{2})\vpravo)$

Pojďme najít hodnotu . $M(n_{i}^{2})$

Zaveďme náhodnou proměnnou , která se rovná 1 , pokud spadne do i -té kapsy, a 0 v opačném případě: $X_{{ij}}$ A[j]

$n_{i}=\součet _{{j=1}}^{n}X_{{ij}}$

${\begin{matrix}M\left(n_{i}^{2}\right)=&M\left[\left(\sum _{{j=1}}^{n}X_{{ij}}\ vpravo)^{2}\right]=M\left[\součet _{{j=1}}^{n}\součet _{{k=1}}^{n}X_{{ij}}X_{ {ik}}\right]=\\\ &\sum _{{j=1}}^{n}M\left[X_{{ij}}^{2}\right]+\součet _{{1 \leq j\leq n}}\ \sum _{{1\leq k\leq n,k\neq j}}M\left[X_{{ij}}X_{{ik}}\right]\end{ matice}}$

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

Jestliže k ≠ j , X ij a X ik jsou nezávislé, tak:

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

Takto

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

Takže očekávaná doba běhu algoritmu řazení do kapsy je

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

Literatura

Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Kapitola 8 Třídění v lineárním čase // Algorithms: Construction and Analysis, 2nd edition = Introduction to Algorithms second edition. - M .: "Williams" , 2005. - S. 230 - 234. - ISBN 5-8459-0857-4 .

Viz také

Seznam třídicích algoritmů

Odkazy

Visualizer1 je Java applet.
Visualizer2 je Java applet.

Algoritmy řazení
Teorie	Složitost O zápis Objednávkový vztah Seřadit typy udržitelného Vnitřní Externí
Výměna	bublina Míchání Trpaslíci Rychle Hřeben Řazení sudé-liché bitový
Výběr	Výběr Pyramidový Hladký
vložky	vložky shella strom
fúze	fúze
Žádné srovnání	Počítací blok
hybridní	introsort Timsort
jiný	Topologické sítí biton
nepraktický	Bogosort Stooge řazení lívanec pomalý