Sortare bloc

Block sort (Pocket sort, basket sort, ing. Bucket sort ) - algoritm de sortare , în care elementele sortate sunt distribuite într-un număr finit de blocuri separate (buzunare, coșuri) astfel încât toate elementele din fiecare bloc următor în ordine să fie întotdeauna mai multe (sau mai puțin) decât în precedentul. Fiecare bloc este apoi sortat separat, fie recursiv prin aceeași metodă, fie cu una diferită. Elementele sunt apoi împinse înapoi în matrice . Acest tip de sortare poate avea un timp de execuție liniar.

Acest algoritm necesită cunoștințe despre natura datelor care urmează să fie sortate, dincolo de funcțiile „comparare” și „swap”, suficiente pentru sortare prin îmbinare, sortare heap, sortare rapidă, sortare shell, sortare prin inserție.

Avantaje: aparține clasei de algoritmi rapizi cu timp de execuție liniar O(N) (pe date de intrare bune).

Dezavantaje: se degradează foarte mult cu un număr mare de elemente puțin diferite, sau pe funcția nereușită de a obține numărul coșului din conținutul elementului. În unele dintre aceste cazuri, pentru șirurile care apar în implementările algoritmului de compresie BWT bazat pe sortarea șirurilor , se dovedește că sortarea rapidă de șiruri de la Sedgwick este mult mai rapidă decât sortarea blocurilor.

Algoritm

Dacă elementele de intrare sunt distribuite uniform , atunci timpul de rulare așteptat al algoritmului de sortare de buzunar este liniar. Acest lucru este posibil datorită anumitor ipoteze despre datele de intrare. Pocketsort presupune că datele de intrare sunt distribuite uniform pe segmentul [0, 1) .

Ideea algoritmului este de a împărți segmentul [0, 1) în n segmente identice (buzunare) și de a împărți n valori de intrare în aceste buzunare. Deoarece numerele de intrare sunt distribuite uniform, se presupune că fiecare buzunar va cădea într-un număr mic de numere. Apoi numerele din buzunare sunt sortate secvenţial. O matrice sortată se obține prin listarea secvențială a elementelor fiecărui buzunar.

Pseudocod

funcția bucket-sort(A, n) este găleți ← matrice nouă de n elemente goale pentru i = 0 până la (lungime (A)-1) introduceți A[i] la sfârșitul găleților matrice [msbits(A[i], k)] pentru i = 0 până la n - 1 do sortarea următoare (găleți[i]) return Buckets de concatenare a matricei[0], ..., buckets[n-1]

Intrarea funcției bucket-sort este o matrice sortabilă (listă, colecție etc.) A și numărul de blocuri - n .

Matricea buckets este o matrice de matrice (o matrice de liste, o matrice de colecții etc.) care se potrivesc cu natura elementelor lui A .

Funcția msbits(x,k) este strâns legată de numărul de blocuri - n (returnează o valoare de la 0 la n) și, în general, returnează cei mai semnificativi k biți din x ( floor(x/2^(size) (x)-k ))) ). Diferite funcții pot fi utilizate ca msbits(x,k) care se potrivesc cu natura datelor sortate și permit împărțirea matricei A în n blocuri. De exemplu, pentru caracterele AZ, aceasta ar putea fi o potrivire cu numerele de litere 0-25 sau poate returna codul primei litere (0-255) pentru setul de caractere ASCII; pentru numerele [0, 1) poate fi funcția floor(n*A[i]) , iar pentru o mulțime arbitrară de numere din intervalul [a, b) poate fi funcția floor (n*(A[i]) ]-a)/(ba )) .

Funcția de sortare următoare implementează, de asemenea, un algoritm de sortare pentru fiecare bloc creat în primul pas. Folosirea recursiv bucket-sort ca următoarea sortare transformă acest algoritm într-o sortare radix . În cazul lui n = 2 , corespunde sortării rapide (deși cu o alegere potențial slabă a pivotului).

Evaluare de dificultate

Să estimăm complexitatea algoritmului de sortare a blocurilor pentru cazul în care sortarea prin inserție este utilizată ca algoritm de sortare a blocurilor (sortarea următoare din pseudocod) .

Pentru a estima complexitatea algoritmului, să introducem o variabilă aleatoare n i , care indică numărul de elemente care vor cădea în buzunar B[i]. Timpul de rulare a sortării prin inserare este . $O\stânga(n^{2}\dreapta)$

Timpul de rulare al algoritmului de sortare de buzunar este

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

Să calculăm așteptările matematice ale ambelor părți ale egalității:

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

Să găsim valoarea . $M(n_{i}^{2})$

Să introducem o variabilă aleatoare , care este egală cu 1 dacă se încadrează în al i -lea buzunar și 0 în caz contrar: $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}}\ dreapta)^{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{ matrice}}$

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

Dacă k ≠ j , X ij și X ik sunt independente, deci:

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

În acest fel

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

Deci, timpul de rulare estimat al algoritmului de sortare de buzunar este

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

Literatură

Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Capitolul 8 Sortarea în timp liniar // Algoritmi: Construcție și analiză, ediția a II-a = Introducere în algoritmi ediția a doua. - M .: „Williams” , 2005. - S. 230 - 234. - ISBN 5-8459-0857-4 .

Vezi și

Lista algoritmilor de sortare

Link -uri

Visualizer1 este un applet Java.
Visualizer2 este un applet Java.

Algoritmi de sortare
Teorie	Complexitate O notație Relația de comandă Sortați tipuri durabil Intern Extern
schimb valutar	bule Agitând Piticii Rapid Pieptene Sortare par-impar Pe bit
Alegere	Alegere Piramidal Neted
inserții	inserții shella copac
fuziune	fuziune
Fara comparatii	Socoteală bloc
hibrid	introsort Timsort
Alte	Topologic retelelor biton
nepractic	Bogosort Soiul de ciudăţeni clătită încet