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

Բլոկային դասակարգում
Տեսակ	ալգորիթմ և տեսակավորման ալգորիթմ
Դաս	տեսակավորման ալգորիթմ
Տվյալների կառուցվածք	$O(n\cdot k)$
Վատագույն դեպքում կատարումը	$O(n^{2})$
Օգտագործում է	զանգված

էլեմենտները բաժանվում են զամբյուղների միջև

այնուհետև յուրաքանչյուր զամբյուղում էլեմենտները դասակարգվում են

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

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

Առավելություններ. պատկանում է ժամանակի գծային կատարմամբ 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_i, որը նշանակում է էլեմենտների քանակ, որոնք կընկնեն B[i] գրպանի մեջ։ Ներդրմամբ դասակարգման աշխատաժամանակը հավասար է $O\left(n^{2}\right)$։

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

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

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

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

Գտնենք $M(n_{i}^{2})$ մեծությունը։

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

$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}\right)^{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{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\leq j\leq n}\ \sum _{1\leq k\leq n,k\neq j}{\frac {1}{n^{2}}}=2-{\frac {1}{n}}$

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

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