Թվային տեսակավորում
Թվային տեսակավորում | |
---|---|
Տեսակ | տեսակավորման ալգորիթմ |
Տվյալների կառուցվածք | |
Վատագույն դեպքում կատարումը | |
Օգտագործում է | զանգված |
Թվային տեսակավորումը հայտնի է որպես հաշվիչային տեսակավորում (չպետք է շփոթել հաշվողական տեսակավորում հետ), որը ալգորիթմների տեսակավորում է և հարմար է տարրերի ցուցակների տեսակավորման համար, որտեղ տարերի թիվը (n) և հնարավոր բանալիների արժեքների թիվը (N) մոտավորապես նույնն են[1]։ Այն պահանջում է 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 և նորից նշանակման զանգված[2]։
Զանգվածը, որտեղ N ավելի երկար է քան n, bucket sort ընդհանրացնում է, որ ավելի արդյունավետ է տարածության և ժամանակի տեսանկյունից։
Դիտեք նաև
[խմբագրել | խմբագրել կոդը]Ծանոթագրություններ
[խմբագրել | խմբագրել կոդը]- ↑ NIST's Dictionary of Algorithms and Data Structures: pigeonhole sort
- ↑ Black, Paul E. (2006 թ․ հունիսի 19). «"pigeonhole sort", in Dictionary of Algorithms and Data Structures [online]». U.S. National Institute of Standards and Technology. Վերցված է 2009 թ․ ապրիլի 26-ին.