Blokkrendezés

Blokkrendezés (Pocket sort, basket sort, eng. Bucket sort ) - rendezési algoritmus , amelyben a rendezett elemek véges számú különálló blokk (zsebek, kosarak) között vannak elosztva úgy, hogy minden következő blokkban sorrendben minden elem mindig több legyen. (vagy kevesebb), mint az előzőben. Ezután minden blokkot külön-külön rendezünk, akár rekurzív módon, akár egy másik módszerrel. Az elemek ezután visszakerülnek a tömbbe . Az ilyen típusú rendezésnek lehet lineáris végrehajtási ideje.

Ehhez az algoritmushoz az "összehasonlítás" és a "csere" függvényeken túlmenően ismerni kell a rendezendő adatok természetét, ami elegendő az összevonási rendezéshez, kupac rendezéshez, gyors rendezéshez, shell rendezéshez, beillesztési rendezéshez.

Előnyök: a lineáris O(N) végrehajtási idővel rendelkező gyors algoritmusok osztályába tartozik (jó bemeneti adatokon).

Hátrányok: sokat ront sok kis különböző elem mellett, vagy az elem tartalmából a kosárszám megszerzésének sikertelen funkcióján. Az esetek némelyikében a BWT -tömörítési algoritmus karakterlánc-rendezésen alapuló implementációiban előforduló karakterláncok esetében kiderül, hogy a Sedgwick-féle karakterláncok gyorsrendezése sokkal gyorsabb, mint a blokkrendezés.

Algoritmus

Ha a bemeneti elemek egyenletes eloszlásúak , akkor a zsebrendezési algoritmus várható futási ideje lineáris. Ez a bemeneti adatokkal kapcsolatos bizonyos feltételezések miatt lehetséges. A Pocketsort feltételezi, hogy a bemeneti adatok egyenletesen oszlanak el a [0, 1) szegmensen .

Az algoritmus lényege, hogy a [0, 1) szegmenst n azonos szegmensre (zsebre) osztja, és n bemeneti értéket oszt ezekre a zsebekre. Mivel a bemeneti számok egyenletesen oszlanak el, feltételezzük, hogy minden zseb kis számú számra esik. Ezután a zsebekben lévő számok sorba rendeződnek. Rendezett tömböt kapunk az egyes zsebek elemeinek szekvenciális felsorolásával.

Pszeudokód

függvény bucket-sort(A, n) az kofák ← n üres elemből álló új tömb ha i = 0 -tól (hossz(A)-1-ig) , illessze be az A[i] -t a tömbök [msbits(A[i], k)] végére, ha i = 0 és n - 1 do következő rendezés(vödrök[i]) return Tömbösszefűzési gyűjtők[0], ..., gyűjtők[n-1]

A bucket-sort függvény bemenete egy rendezhető tömb (lista, gyűjtemény stb.) A és a blokkok száma - n .

A buckets tömb olyan tömbök tömbje (listák tömbje, gyűjtemények tömbje stb.), amelyek megfelelnek az A elemeinek természetének .

Az msbits(x,k) függvény szorosan kapcsolódik a blokkok számához - n (értéket ad vissza 0-tól n-ig), és általában a k legjelentősebb bitet adja vissza x -ből ( floor(x/2^(size) (x)-k ))) ). Különféle függvények használhatók msbit(x,k)-ként, amelyek megfelelnek a rendezett adatok természetének, és lehetővé teszik az A tömb n blokkra való felosztását. Például AZ karakterek esetén ez lehet egyezés a 0-25 betűszámokkal, vagy visszaadhatja az első betű kódját (0-255) az ASCII-karakterkészlethez; a [0, 1) számoknál lehet a padló(n*A[i]) , az [a, b) intervallumban lévő tetszőleges számhalmaznál pedig az (n* ( A[i]) függvény ]-a)/(ba )) .

A next-sort funkció egy rendezési algoritmust is megvalósít az első lépésben létrehozott minden egyes blokkhoz. A bucket-sort rekurzív használata következő rendezésként ezt az algoritmust radix rendezéssé változtatja . n = 2 esetén a gyorsrendezésnek felel meg (bár potenciálisan rossz pivot-választással).

Nehézségi fok

Becsüljük meg a blokkrendezési algoritmus összetettségét arra az esetre, amikor a beillesztési rendezést blokkrendezési algoritmusként használjuk ( következő rendezés pszeudokódból) .

Az algoritmus bonyolultságának becsléséhez vezessünk be egy n i valószínűségi változót , amely a zsebbe kerülő elemek számát jelöli . A beillesztési rendezés futási ideje . B[i] $O\bal(n^{2}\jobb)$

A zsebrendezési algoritmus futási ideje a

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

Számítsuk ki az egyenlőség mindkét részének matematikai elvárását :

$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\bal(M(n_{i}^{2})\jobb)$

Keressük az értéket . $M(n_{i}^{2})$

Vezessünk be egy valószínűségi változót , amely egyenlő 1 -gyel, ha az i -edik zsebbe esik , és 0 -val egyébként: $X_{{ij}}$ A[j]

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

${\begin{mátrix}M\left(n_{i}^{2}\right)=&M\left[\left(\sum _{{j=1}}^{n}X_{{ij}}\ jobb)^{2}\right]=M\left[\sum _{{j=1}}^{n}\sum _{{k=1}}^{n}X_{{ij}}X_{ {ik}}\right]=\\\ &\sum _{{j=1}}^{n}M\left[X_{{ij}}^{2}\right]+\sum _{{1 \leq j\leq n}}\ \sum _{{1\leq k\leq n,k\neq j}}M\left[X_{{ij}}X_{{ik}}\right]\end{ mátrix}}$

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

Ha k ≠ j , X ij és X ik függetlenek, akkor:

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

Ily módon

$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}}$

Tehát a zsebrendezési algoritmus várható futási ideje:

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

Irodalom

Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. 8. fejezet Rendezés lineáris időben // Algoritmusok: Konstrukció és elemzés, 2. kiadás = Bevezetés az algoritmusokba, második kiadás. - M .: "Williams" , 2005. - S. 230 - 234. - ISBN 5-8459-0857-4 .

Lásd még

A rendezési algoritmusok listája

Linkek

A Visualizer1 egy Java kisalkalmazás.
A Visualizer2 egy Java kisalkalmazás.

Rendezési algoritmusok
Elmélet	Bonyolultság O jelölés Rendelési viszony Típusok rendezése fenntartható Belső Külső
Csere	buborék Keverés Törpék Gyors Fésű Rendezés páros-páratlan Bitenként
Választás	Választás Piramis alakú Sima
Betétek	Betétek shella fa
egyesülés	egyesülés
Nincs összehasonlítás	Számolás Blokk
hibrid	introsort Timsort
Egyéb	Topológiai hálózatok biton
nem praktikus	Bogosort Stooge fajta palacsinta lassú