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

Թվային տեսակավորումը հայտնի է որպես հաշվիչային տեսակավորում (չպետք է շփոթել հաշվողական տեսակավորում հետ), որը ալգորիթմների տեսակավորում է և հարմար է տարրերի ցուցակների տեսակավորման համար, որտեղ տարերի թիվը (n) և հնարավոր բանալիների արժեքների թիվը (N) մոտավորապես նույնն են: Այն պահանջում է O(n + N) ժամանակ:

Թվային ալգորիթմը աշխատում է հետևյալ կերպ:

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

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

• (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 ընդհանրացնում է, որ ավելի արդյունավետ է տարածության և ժամանակի տեսանկյունից:

Դիտեք նաև

• Թվային սկզբունք