Բլոկային դասակարգում

աջից|շրջափակել|էլեմենտները բաժանվում են զամբյուղների միջև
աջից|շրջափակել|այնուհետև յուրաքանչյուր զամբյուղում էլեմենտները դասակարգվում են

**Բլոկային դասակարգումը** (Գրպանային դասակարգում, զամբյուղային դասակարգում, )՝ դասակարգման ալգորիթմ, որում դասակարգվող էլեմենտները բաժանվում են վերջավոր թվով առանձին բլոկների միջև (գրպանների, զամբյուղների) այնպես, որ յուրաքանչյուր հերթականությամբ հաջորդ բլոկում էլեմենտները ավելի շատ լինեն (կամ քիչ), քան նախորդում։ Այնուհետև յուրաքանչյուր բլոկը դասակարգվում է առանձին, կամ նույն մեթոդով, կամ ուրիշ։ Այնուհետև էլեմենտները տեղափոխվում են ետ՝ զանգված։ Դասակարգման այս տեսակը կարող է ունենալ ժամանակի գծային կատարում։

Այս ալգորիթմը գիտելիքներ է պահանջում դասակարգվող տվյալների մասին, որոնք դուրս են գալիս "համեմատել" և "տեղերով փոխել" ֆունկցիայի սահմաններից, բավարար միաձուլմամբ դասակարգման, բրգային դասակարգման, արագ դասակարգման, Շելլի դասակարգման, ներդրմամբ դասակարգման համար։

Առավելություններ. պատկանում է ժամանակի գծային կատարմամբ O(N) արագ ալգորիթմների դասին (տվյալների հաջողակ ելքով)։

Թերություններ. կտրուկ վատանում է մեծ քանակությամբ իրարից քիչ տարբերվող էլեմենտների, կամ պարունակվող էլեմենտով զամբյուղի համարի ստացման անհաջող ֆունկցիայի առկայության ժամանակ։
Մի քանի նմանատիպ դեպքերում տողերի համար, որոնք առաջանում են իրականացումներում հիմնված սեղման ալգորիթմի տողերի դասակարգման վրա BWT, հրաժարվում են, որ տողերի արագ դասակարդումը Սեջվիկի տարբերակում զգալիորեն արագությամբ գերազանցում են բլոկային դասակարգմանը։

## Ալգորիթմ
Եթե մուտքային էլեմենտները ենթարկվում են հավասարաչափ բաշխման օրենքին, ապա գրպանային դասակարգման ալգորիթմի աշխատաժամանակի մաթեմատիկական սպասումը հանդիսանում է գծային։ Դա հնարավոր է որոշակի ենթադրություւներով մուտքային տվյալների մասին։ Գրպանային դասակարգման ժամանակ ենթադրվում է, որ մուտքային տվյալները հավասարաչափ են բաշխված [0, 1) հատվածում։

Ալգորիթմի իմաստն այն է, որ л [0, 1) ինտերվալը բաժանվի *n* հավասար հատվածների (գրպանների), և այդ գրպանների միջև բաժանվի *n* մուտքային մեծություններ։ Քանի որ մուտքային թվերը հավասարաչափ են բաշխված, ենթադրվում է, որ յուրաքանչյուր գրպանի մեջ ընկնում է թվերի ոչ մեծ քանակություն։ Այնուհետև թվերը հերթականությամբ դասակարգվում են գրպաններում։ Դասակարգված զանգված ստացվում է յուրաքանչյուր գրպանի էլեմենտների հաջորդաբար թվարկմամբ։

## Ալգորիթմների բնութագրման լեզու
 **function** bucket-sort(A, n) **is**
 buckets ← n դատարկ էլեմենտներից նոր զանգված
 **for** i = 0 **to** (length(A)-1) **do**
 դնել *A[i]* զանգվածի վերջում buckets[msbits(A[i], k)]
 **for** i = 0 **to** n - 1 **do**
 next-sort(buckets[i])
 **return** Конкатенация զանգվածների buckets[0], ..., buckets[n-1]

*bucket-sort* ֆունկցիայի մուտքում տրվում է դասակարգվող զանգվածը (ցանկ, հավաքածուներ և նմանատիպ) *A* և բլոկների թիվը ` *n*:

*buckets* զանգվածը իրենից ներկայացնում է զանգվածների զանգված (ցանկի զանգված, հավաքածուների զանգված և այլն ), որոնք իրենց տեսակով համապատասխանում են *A* էլեմենտներին։

*msbits(x, k)* ֆունկցիան սերտորեն կապված է բլոկների քանակի հետ ` *n* (վերադարձնում է 0-ից n արժեքներ), և ընդհանուր առմամբ, վերադարձնում է *k* առավել կարևոր բիթերը *x*-ից (*floor(x/2^(size(x)-k))*)։ Որպես *msbits(x, k)* կարող են օգտագործվել տարատեսակ ֆունկցիաներ, որոնք համապատասխանում են դասակարգվող տվյալների տեսակին և թույլատրող A զանգվածը բաժանել n բլոկների։ Օրինակ A-Z սիմվոլների համար դա կարող է լինել տառերին զուգադրված 0-25 թվեր, կամ առաջին տառի կոդի վերադարձը (0-255) ASCII սիմվոլների հավաքածուի համար։ [0, 1) թվերի համար դա կարող է լինել *floor(n*A[i])* ֆունկցիան, իսկ կամայական թվերի հավաքածուի համար [a, b) ինտերվալում ՝ *floor(n*(A[i]-a)/(b-a))* ֆունկցիան.

*next-sort* ֆունկցիան նույնպես իրականացնում է դասակարգման ալգորիթմ առաջին պարբերաշրջանում ստեղծված յուրաքանչյուր բլոկի համար։*bucket-sort*-ի ռեկուրսիվ օգտագործումը որպես *next-sort* վեր է ածում տվյալ ալգորիթմը поразрядную դասակարգման։ *n = 2* դեպքում համապատասխանում է արագ դասակարգման (թեկուզ և հենման էլեմենտի պոտենցիալ սխալ ընտրության դեպքում)։

## Բարդության գնահատական
Գնահատենք բլոկային դասակարգման ալգորիթմի բարդությունը այն դեպքի համար, որի ժամանակ որպես բլոկների դասակարգման ալգորիթմ (*next-sort* ալգորիթմների բնութագրման լեզվից) օգտագործվում է ներդրմամբ դասակարգումը։

Ալգորիթմի դժվարության գնահատման համար մտցնենք պատահական մեծություն *n<sub>i</sub>*, որը նշանակում է էլեմենտների քանակ, որոնք կընկնեն `B[i]` գրպանի մեջ։ Ներդրմամբ դասակարգման աշխատաժամանակը հավասար է O\left(n^2\right)։

Գրպանային դասակարգմամբ ալգորիթմի աշխատաժամանակը հավասար է.

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

Հաշվենք հավասարման երկու մասերի մաթեմատիկական սպասումը .


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


Գտնենք M(n_i^2) մեծությունը։

Մտցնենք պատահական X_{ij} մեծությունը, որը հավասար է 1, եթո `A[j]` ընկնի *i*-ին գրպան, և 0 հակառակ դեպքում .

n_i=\sum_{j=1}^nX_{ij} 


\begin{matrix}
M\left(n_i^2\right)= & M\left[\left(\sum_{j=1}^nX_{ij}\right)^2\right]=M\left[\sum_{j=1}^n\sum_{k=1}^nX_{ij}X_{ik}\right]= 
\\ \ & \sum_{j=1}^nM\left[X_{ij}^2\right]+\sum_{1\le j\le n}\ \sum_{1\le k\le n, k\ne j}M\left[X_{ij}X_{ik}\right]
\end{matrix}


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

Եթե *k ≠ j*, *X**ij* և *X**ik* մեծությունները անկախ են, այդ պատճառով.

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

Այս կերպ


M\left(n_i^2\right)=\sum_{j=1}^{n}\frac{1}{n}+\sum_{1\le j\le n}\ \sum_{1\le k\le n, k\ne j}\frac{1}{n^2}=2-\frac{1}{n}


Այսպիսով, Գրպանային դասակարգմամբ ալգորիթմի աշխատաժամանակը հավասար է

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

Կատեգորիա:Դասակարգման ալգորիթմներ