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

'''Հաշվողական տեսակավորումը''' [[տեսակավորման ալգորիթմ]] է, որում օգտագործվում է տեսակավորվող [[զանգվածի]] թվերի շարքը` համընկնող էլեմենտների տեսակավորման համար:համար։ Հաշվողական տեսակավորման կիրառությունը ամբողջական է միայն այն ժամանակ, երբ տեսակավորվող թվերն ունեն հնարավոր նշանակության շարքեր, որը բավականին փոքր է տեսակավորվող բազմության հետ համեմատած, օրինակ` 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> անգամ:անգամ։

Այս տարբերակը ({{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>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>:։ Ալգորիթմը կայուն է:է։

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

Առաջին երկու ալգորիթմերում առաջին երկու ցիկլերը աշխատում են համապատասխանաբար [[Теория сложности вычислений|<math>\Theta(k)</math>]] և <math>\Theta(n)</math> համար, կրկնակի ցիկլը` <math>\Theta(n + k)</math> համար:համար։ Երրորդ ալգորիթմում ցիկլը զբաղեցնում են համապատասխանաբար <math>\Theta(k)</math>, <math>\Theta(n)</math>, <math>\Theta(k)</math> և <math>\Theta(n)</math>: Արդյունքում` բոլոր երեք ալգորիթմերն էլ ունեն գծային ժամանակավոր <math>\Theta(n + k)</math> աշխատունակություն:աշխատունակություն։ Առաջին երկու ալգորիթմերում օգտագործվող հիշողությունը հավասար է <math>\Theta(k)</math>, իսկ երրորդում` <math>\Theta(n + k)</math>:

Այստեղ օգտագործվում են մուտքային <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>: Ալգորիթմը կայուն է:է։

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

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