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

Վիքիպեդիայից՝ ազատ հանրագիտարանից

Թվային տեսակավորումը հայտնի է որպես հաշվիչային տեսակավորում (չպետք է շփոթել հաշվողական տեսակավորում հետ), որը ալգորիթմների տեսակավորում է և հարմար է տարրերի ցուցակների տեսակավորման համար, որտեղ տարերի թիվը (n) և հնարավոր բանալիների արժեքների թիվը (N) մոտավորապես նույնն են։[1] Այն պահանջում է 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 և նորից նշանակման զանգված։[2]

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

Դիտեք նաև[խմբագրել]

Հղումներ[խմբագրել]

  1. NIST's Dictionary of Algorithms and Data Structures: pigeonhole sort
  2. Black, Paul E. (2006-06-19)։ «"pigeonhole sort", in Dictionary of Algorithms and Data Structures [online»]։ U.S. National Institute of Standards and Technology։ http://www.itl.nist.gov/div897/sqg/dads/HTML/pigeonholeSort.html։ Վերցված է 2009-04-26։ 
Վիքիդարանի պատկերանիշը
Անգլերեն Վիքիդարանում կան նյութեր այս թեմայով՝
Sorting/Pigeonhole sort