Jump to content

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

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Թվային տեսակավորում
Տեսակտեսակավորման ալգորիթմ
Տվյալների կառուցվածք
Վատագույն դեպքում կատարումը
Օգտագործում էզանգված

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

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

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

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

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

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

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

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

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

  • 3։ 1
  • 4։ 0
  • 5։ 2
  • 6։ 0
  • 7։ 0
  • 8։ 1

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

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

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

[խմբագրել | խմբագրել կոդը]
  1. NIST's Dictionary of Algorithms and Data Structures: pigeonhole sort
  2. 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-ին.