«Հաշվողական տեսակավորում»–ի խմբագրումների տարբերություն
Content deleted Content added
Նոր էջ. '''Հաշվողական տեսակավորումը'' տեսակավորման ալգորիթմ է, որում օգտագործվում է տեսակավորվող [[զանգված... |
No edit summary |
||
Տող 1.
'''Հաշվողական տեսակավորումը'' [[տեսակավորման ալգորիթմ]] է, որում օգտագործվում է տեսակավորվող [[զանգվածի]] թվերի շարքը` համընկնող էլեմենտների տեսակավորման համար: Հաշվողական տեսակավորման կիրառությունը ամբողջական է միայն այն ժամանակ, երբ տեսակավորվող թվերն ունեն հնարավոր նշանակության շարքեր, որը բավականին փոքր է տեսակավորվող բազմության հետ համեմատած, օրինակ` 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>
SimpleCountingSort
for i = 0 to k - 1
C[i] = 0;
for i = 0 to n - 1
C[A[i]] = C[A[i]] + 1;
b = 0;
for j = 0 to k - 1
for i = 0 to C[j] - 1
A[b] = j;
b = b + 1;</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>
ListCountingSort
for i = 0 to k - 1
C[i] = NULL;
for i = 0 to n - 1
C[A[i].key].add(A[i]);
b = 0;
for j = 0 to k - 1
p = C[j];
while p != NULL
A[b] = p.data;
p = p.next();
b = b + 1;</code>
| |||