Estä lajittelu

Lohkojen lajittelu (Pocket sort, basket sort, eng. Bucket sort ) - lajittelualgoritmi , jossa lajitellut elementit jaetaan rajalliseen määrään erillisiä lohkoja (taskuja, koreja) siten, että jokaisen seuraavan lohkon kaikki elementit ovat aina enemmän (tai vähemmän) kuin edellisessä. Jokainen lohko lajitellaan sitten erikseen, joko rekursiivisesti samalla menetelmällä tai eri menetelmällä. Elementit työnnetään sitten takaisin taulukkoon . Tämän tyyppisellä lajittelulla voi olla lineaarinen suoritusaika.

Tämä algoritmi vaatii tietoa lajiteltavien tietojen luonteesta, "vertaa"- ja "swap"-toimintojen lisäksi, riittää yhdistämiseen, keon lajitteluun, pikalajitteluun, komentotulkkilajitteluun, lisäyslajitteluun.

Edut: kuuluu nopeiden algoritmien luokkaan, jossa on lineaarinen O(N) suoritusaika (hyvillä syöttötiedoilla).

Haitat: se huonontaa paljon suurella määrällä pieniä erilaisia elementtejä tai epäonnistuneesta toiminnosta saada korinumero elementin sisällöstä. Joissakin näistä tapauksista merkkijonojen osalta, joita esiintyy merkkijonojen lajitteluun perustuvan BWT -pakkausalgoritmin toteutuksissa , käy ilmi, että Sedgwickin merkkijonojen pikalajittelu on nopeudeltaan paljon nopeampi kuin lohkolajittelu .

Algoritmi

Jos syöteelementit jakautuvat tasaisesti , taskulajittelualgoritmin odotettu ajoaika on lineaarinen. Tämä on mahdollista syötetietoihin liittyvien tiettyjen oletusten vuoksi. Pocketsort olettaa, että syöttödata on jakautunut tasaisesti segmentille [0, 1 ) .

Algoritmin ideana on jakaa segmentti [0, 1) n identtiseksi segmentiksi ( taskuksi ) ja jakaa n syöttöarvoa näihin taskuihin. Koska syötetyt numerot jakautuvat tasaisesti, oletetaan, että jokainen tasku jakautuu pieneen määrään numeroita. Sitten taskuissa olevat numerot lajitellaan peräkkäin. Lajiteltu taulukko saadaan luettelemalla kunkin taskun elementit peräkkäin.

Pseudokoodi

funktio bucket-sort(A, n) on buckets ← uusi joukko n tyhjää elementtiä jos i = 0 arvoon (pituus(A)-1) , lisää A[i] taulukon ryhmien [msbits(A[i], k)] loppuun, jos i = 0 - n - 1 do seuraava lajittelu(ämpärit[i]) return Array concatenation buckets[0], ..., buckets[n-1]

Bucket-sort- funktion syöte on lajiteltava taulukko (luettelo, kokoelma jne.) A ja lohkojen lukumäärä - n .

Buckets array on joukko taulukoita (luettelot, joukko kokoelmat jne.), jotka vastaavat A :n elementtien luonnetta .

Funktio msbits(x,k) liittyy läheisesti lohkojen määrään - n (palauttaa arvon 0:sta n:ään) ja yleensä palauttaa k merkittävintä bittiä x :stä ( floor(x/2^(size) (x)-k ))) ). Erilaisia funktioita voidaan käyttää msbiteinä (x,k) , jotka vastaavat lajitellun tiedon luonnetta ja mahdollistavat taulukon A jakamisen n lohkoon. Esimerkiksi AZ-merkkien kohdalla tämä voi vastata kirjainnumeroita 0-25 tai palauttaa ensimmäisen kirjaimen koodin (0-255) ASCII-merkistölle. numeroille [0, 1) se voi olla funktio kerros(n*A[i]) ja mielivaltaiselle lukujoukolle välissä [a, b) se voi olla funktion kerros (n*(A[i] ) ]-a)/(ba)) .

Seuraava lajittelu -toiminto toteuttaa myös lajittelualgoritmin jokaiselle ensimmäisessä vaiheessa luodulle lohkolle. Rekursiivinen bucket-lajittelun käyttäminen seuraavan lajittelun muodossa muuttaa tämän algoritmin kantalukulajitteluksi . Tapauksessa n = 2 , se vastaa pikalajittelua (vaikkakin mahdollisesti huonolla kääntöpisteen valinnalla).

Vaikeusaste

Arvioidaan lohkolajittelualgoritmin monimutkaisuus siinä tapauksessa, että lisäyslajittelua käytetään lohkolajittelualgoritmina ( seuraava lajittelu pseudokoodista) .

Algoritmin monimutkaisuuden arvioimiseksi otetaan käyttöön satunnaismuuttuja n i , joka ilmaisee taskuun putoavien elementtien lukumäärää B[i]. Lisäyslajittelun suoritusaika on . $O\vasen(n^{2}\oikea)$

Taskulajittelualgoritmin ajoaika on

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

Lasketaan tasa-arvon molempien osien matemaattinen odotus :

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

Etsitään arvo . $M(n_{i}^{2})$

Otetaan käyttöön satunnaismuuttuja , joka on yhtä suuri kuin 1 , jos se putoaa i - taskuun, ja 0 muussa tapauksessa: $X_{{ij}}$ A[j]

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

${\begin{matrix}M\left(n_{i}^{2}\right)=&M\left[\left(\sum _{{j=1}}^{n}X_{{ij}}\ oikea)^{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}}\oikea]\end{ matriisi}}$

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

Jos k ≠ j , X ij ja X ik ovat riippumattomia, niin:

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

Tällä tavalla

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

Joten taskulajittelualgoritmin odotettu ajoaika on

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

Kirjallisuus

Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Luku 8 Lajittelu lineaarisessa ajassa // Algoritmit: Rakentaminen ja analyysi, 2. painos = Algoritmien johdatus, toinen painos. - M .: "Williams" , 2005. - S. 230 - 234. - ISBN 5-8459-0857-4 .

Katso myös

Luettelo lajittelualgoritmeista

Linkit

Visualizer1 on Java-sovelma.
Visualizer2 on Java-sovelma.

Lajittelualgoritmit
Teoria	Monimutkaisuus O merkintä Tilaussuhde Lajittele tyypit kestävää Sisäinen Ulkoinen
Vaihto	kupla Sekoitetaan Kääpiöt Nopeasti Kampa Lajittelu parillinen-pariton Bitittain
Valinta	Valinta Pyramidin muotoinen Sileä
insertit	insertit shella puu
fuusio	fuusio
Ei vertailuja	Laskenta lohko
hybridi	introsort Timsort
muu	Topologinen verkkoja bitonia
epäkäytännöllistä	Bogosort Stooge lajittelu pannukakku hidas