«Հաշվողական տեսակավորում»–ի խմբագրումների տարբերություն

'''Հաշվողական տեսակավորումը''' [[տեսակավորման ալգորիթմ]] է, որում օգտագործվում է տեսակավորվող [[զանգվածի]] թվերի շարքը՝ համընկնող էլեմենտների տեսակավորման համար։ Հաշվողական տեսակավորման կիրառությունը ամբողջական է միայն այն ժամանակ, երբ տեսակավորվող թվերն ունեն հնարավոր նշանակության շարքեր, որը բավականին փոքր է տեսակավորվող բազմության հետ համեմատած, օրինակ՝ 1000-ից փոքր միլիոն բնական թվեր։ Ալգորիթմի արդյունավետությունը նվազում է, եթե մի քնի տարբեր էլեմենտների մեկ բջջի մեջ ընկնելու դեպքում անհրաժեշտ է լինում դրանք կրկին տեսակավորել։ Բջջի ներսում տեսակավորման անհրաժեշտությունը կորցնում է ալգորիթմի իմաստը, քանի որ յուրաքանչյուր էլեմենտ ստիպված կլինենք դիտարկել մեկ անգամից ավելի։

Ենթադրենք, որ մուտքային զանգվածը բաղկացած է <math>n</math> հատ ամբողջ թվերից՝0-ից <math>k - 1</math> միջակայքում, որտեղ <math>k \in \mathbb N</math>։ Հետագայում ալգորիթմը կընդհանրացվի կամայակն ամբողջ թվերի շարքի համար։ Գոյություն ունեն մի քանի հաշվողական տեսակավորման ձևեր. ներքևում դիտարկված են երեք գծային և մեկ քառակուսային ձևեր։ Վերջինս օգտագործում է այլ մոտեցում, բայց ունի նույն իմաստը։

 

== Պարզ ալգորիթմ ==

Սա ալգորիթմի պարզագույն տեսակն է։ Ստեղծել զրոներից բաղկացած օժանդակ <code>C[0..k - 1]</code> զանգված, այնուհետև հաջորդականությամբ կարդալ մուտքային <code>A</code> մատրիցի էլեմենտները, յուրաքանչյուր <code>A[i]</code> համար ընդլայնել <code>C[A[i]]</code> մեկ միավորով։ Այժմ բավարար է անցնել <code>C</code> մատրիցով, յուրաքանչյուր <math>j \in \{0, ..., k - 1\}</math> համար <code>A</code> մատրիցում համապատասխանաբար գրել <code>j թիվը C[j]</code> անգամ։

<code>

 

== Ցուցակով ալգորիթմ ==

Այս տարբերակը ({{lang-en|pigeonhole sorting, count sort}}) օգտագործվում է, երբ մուտքին տրվում է տվյալների ստրուկտուրային զանգված, որն անհրաժեշտ է տեսակավորել ըստ բանալիների (<code>key</code>)։ Անհրաժեշտ է ստեղծել օժանդակ <code>C[0..k - 1]</code> զանգված, հետագայում յուրաքանչյուր <code>C[i]</code> կպարունակի մուտքային զանգվածի էլեմենտների ցանկը։ Այնուհետև հերթականությամբ կարդալ մուտքային <code>A</code> զանգվածի էլեմենտները, յուրաքանչյուր <code>A[i]</code> ավելացնել <code>C[A[i].key]</code> զանգվածի մեջ։ Վերջում անցնել <code>C</code> զանգվածով, յուրաքանչյուր <math>j \in \{0, ..., k - 1\}</math> համար <code>A</code> զանգվածում համապատասխանաբար գրել <code>C[j]</code> էլեմենտները։ [[կայուն ալգորիթմ|Ալգորիթմը կայուն է]].

<code>

 

== Կայուն ալգորիթմ ==

Այս տարբերակում բացի մուտքային <code>A</code> զանգվածից անհրաժեշտ կլինեն երկու օժանդակ զանգվածներ՝ <code>C[0..k - 1]</code> հաշվիչի համար, և <code>B[0..n - 1]</code>` տեսակավորված զանգվածի համար։ Սկզբում պետք է <code>C</code> զանգվածում լրացնել զրոներ, և յուրաքանչյուր <code>A[i]</code> համար <code>C[A[i]]</code> մեծացնել մեկով։ Այնուհետև հաշվարկվում է էլեմենտների թիվը` ընթացիկից փոքր կամ հավասար։ Դրա համար յուրաքանչյուր <code>C[j]</code>, սկսած <code>C[1]</code>-ից, ընդլայնում են <code>C[j - 1]</code>-ով։ Ալգորիթմի վերջին քայլում կարդում են մուտքային զանգվածը վերջից, <code>C[A[i]]</code> նշանակությունը փոքրացվում է մեկով, և յուրաքանչյուր <code>B[C[A[i]]]</code>-ում գրանցվում է code>A[i]</code>։ Ալգորիթմը կայուն է։

<code>

 

== Կամայական ամբողջ թվերի շարքի ընդհանրացում ==

Այստեղ ծագում են մի քանի հարցեր. ինչ անել, եթե արժեքների (min и max) շարքերը նախապես հայտնի չեն։ Ինչ անել, եթե մինիմալ արժեքները մեծ են զրոյից կամ տեսակավորվող տվյալներում առկա են բացասական թվեր։ Առաջին հարցը կարելի է որոշել min-ի և max-ի գծային փնտրմամբ, որը չի ազդի ալգորիթմի ասիմետրիկայի վրա։ Երկրորդ հարցը մի փոքր ավելի բարդ է։ Եթե min-ը մեծ է զրոյից, ապա անհրաժեշտ է <code>C</code> զանգվածի հետ աշխատելիս <code>A[i]</code>-ից դուրս բերել min-ը, իսկ հակառակ դեպքում՝ ավելացնել։ Բացասական թվերի առկայության դեպքում <code>C</code> զանգվածի հետ աշխատանքի ժամանակ պետք է <code>A[i]</code>-ին ավելացնել |min|, իսկ հակառակ գրանցման դեպքում՝ դուրս բերել։

 

== Վերլուծություն ==

 

== Հաշվողական տեսակավորման քառակուսային ալգորիթմ ==

Այստեղ օգտագործվում են մուտքային <code>A</code> զանգվածը և <code>B</code> օժանդակ զանգվածը՝ տեսակավորված բազմության համար։ Ալգորիթմում անհրաժեշտ է <code>A[i]</code> մուտքային զանգվածի յուրաքանչյուր էլեմենտի համար հաշվարկել <math>c_1</math>-ից փոքր էլեմենտների թիվը, և դրան հավասար, բայց <math>c_2</math> (<math>c = c_1 + c_2</math>)-ից առաջ գտնվող էլեմենտների թիվը։ Այնուհետև <code>B[c]</code> փոխանցել <code>A[i]</code>։ Ալգորիթմը կայուն է։

<code>

 

=== Վերլուծություն ===

Ակնհայտ է, որ ալգորիթմի ժամաննակավոր գնահատականը հավասար է <math>\Theta(n^2)</math>, հիշողությունը՝ <math>\Theta(n)</math>։

 

== Իրագործման օրինակներ ==

=== C ===

Պարզ ալգորիթմ։

 

=== C# ===

Հաշվողական տեսակավորման քառակուսային ալգորիթմ

<source lang="csharp">