Թվային տեսակավորում

Թվային տեսակավորումը հայտնի է որպես հաշվիչային տեսակավորում (չպետք է շփոթել հաշվողական տեսակավորում հետ), որը ալգորիթմների տեսակավորում է և հարմար է տարրերի ցուցակների տեսակավորման համար, որտեղ տարերի թիվը (n) և հնարավոր բանալիների արժեքների թիվը (N) մոտավորապես նույնն ենNIST's Dictionary of Algorithms and Data Structures: pigeonhole sort։ Այն պահանջում է O(n + N) ժամանակ։

Թվային ալգորիթմը աշխատում է հետևյալ կերպ։
 Տրվում է զանգվածային արժեքներ, որոնք պետք է տեսակավորվեն և ստեղծվեն ի սկզբանե դատարկ "թվային," օժանդակ զանգված, մեկ թիվ յուրաքանչյուր բանալու համար սկզբնական շարքի միջոցով։
 Անդրարառնալով սկզբնական զանգվածին, դնել յուրաքանչյուր թվային զանգվածը համապատասխան բանալու վրա, այնպես որ յուրաքանչյուր դասակարգում ի վերջո պարունակի բոլոր արժեքների ցանկը այդ բանալու հետ։
 Կրկնել թվային զանգվածի դասակարգումը ավելի նպատակայնորեն, և հետ դնել թվային զանգվածի ոչ դատարկ տարրերը դեպի սկզբնական զանգված։

Օրինակ, ենթադրենք մենք տեսակավորել ենք այս զույգ արժեքները ըստ իրենց առաջին տարրերի։

 (5, "բարև")
 (3, "կարկանդակ")
 (8, "խնձոր")
 (5, "թագավոր")

Մենք սկսում ենք թվային դասակրգումը 3 և 8 միջև յուրաքնաչյուր արժեքի համար, հետո տեղափոխում ենք յուրաքանչյուր տարր իր թվային դասակարգման մեջ։

 3։ (3, "կարկանդակ")
 4։
 5։ (5, "բարև"), (5, "թագավոր")
 6։
 7։
 8։ (8, "խնձոր")

Հետո մենք կկրկնենք թվային զանգվածի դասակարգումը ավելի նպատակայնորեն և կտեղափոխենք նրանց հետ սկզբնական ցանկ։

Տարբերությունը թվային տեսակավորման և հաշվիչային տեսակավորման այն է, որ հաշվիչային տեսակավորումը չի պարունակում օժանդակ զանգվածին մուտքագրված տարրերի ցուցակները։

 3։ 1
 4։ 0
 5։ 2
 6։ 0
 7։ 0
 8։ 1
Օգտագործելով այս ինֆորմացիան մենք կարող ենք իրականացնել մի շարք փոփոխություններ մուտքագրված զանգվածի վրա, շարժելով տարրերը միայն մեկ անգամ։ Դրան հակառակ թվային տեսակավորումը շարժում է տարրերը երկու անգամ՝ առաջինը թվայինի/bucket sort և նորից նշանակման զանգված։

Զանգվածը, որտեղ N ավելի երկար է քան n, bucket sort ընդհանրացնում է, որ ավելի արդյունավետ է տարածության և ժամանակի տեսանկյունից։

 Դիտեք նաև 
 Թվային սկզբունք

 Ծանոթագրություններ 

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

ru:Сортировка подсчётом#Алгоритм со списком