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

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

Կարգային տեսակավորում[խմբագրել]

Համակարգչային գիտության մեջ կարգային տեսկավորման ալգորիթմը տեսակավորում է թվերը ըստ կարգերի։ Գոյություն ունի տեսակավորման երկու մեթոդ`

  • Least significant digit radix sort (LSD)
  • Most sidnificant digit radix sort (MSD)

LSD տեսակավորման դեպքում սկզբում տեսակավորվում են փոքր կարգերը, հետո մեծերը։ MSD տեսակավորման դեպքում ճիշտ հակառակն է։ LSD տեսակավորման դեպքում ստացվում է հետևյալ պատկերը` Կարճ բանալիները երկարներից առաջ են կանգնում, իսկ միևնույն չափի բանալիները տեսակավորվում են այբբենական կարգով, սա համընկնում է թվերի նորմալ դասակարգման հետ` «1, 2, 3, 4, 5, 6, 7, 8, 9, 10»: MSD տեսակավորման դեպքում ստացվում է այբբենական կարգ, որը հարմար է տողերի տեսակավորման համար : Օրինակ «b, c, d, e, f, g, h, i, j, ba» կտեսակավորվի «b, ba, c, d, e, f, g, h, i, j»: Եթե համադրենք տեսակավորման այս երկու մեթոդները, ապա կստանանք « 1, 10, 2, 3, 4, 5, 6, 7, 8, 9»:

Արդյունավետություն[խմբագրել]

Կարգային տեսակավորման արդյունավետությունը O(kn)է n բանալիների համար, որոնք ունեն k կամ ավելի քիչ թվանշան։ Պետք է հաշվի առնել այն փաստը, որ պարտադիր չէ, որ սա ավելի լավը լինի քան O(n*log(n)), ինչպես k կարող է լինել անկախ n-ից։ Օրինակ ենթադրանք ցանկը n չափանի է, որտեղ n ամբողջ թվերը լոգարիթմել ենք B հիմքով, հետևաբար հնարավոր են B տարբեր թվանշաններ, որտեղ`

  • K >= logB(n)։ Մյուս կողմից էլ եթե կան B տարբեր թվեր, ուրեմն անհրաժեշտ է B հատ ուղղանկյուն, որտեղ միջինում n*log2(B) համեմատություններով հնարավոր կլինի բաշխել այդ ուղղանկյունների մեջ։
  • Ամեն անցում պահանջում է միջինում n*log2(B) համեմատություն

LSD[խմբագրել]

LSD կարգային տեսակավորումը գործում է O(nk) ժամանակում, որտեղ n բանալիների թիվն է, իսկ k բանալիի միջին երկարությունը։

Բացատրություն[խմբագրել]

Յուրաքանչյուր բանալի պայմանականորեն դրվում է մի ուղղանկյունու մեջ, որը կապված է աջակողմյան ուղղանկյունու արժեքի հետ։ Գոյություն ունի ուղղակի կապվածություն թվերի և ուղղանկյան մեջ թվանշանի արժեքի միջև։ Պրոցեսը կրկնվում է հարևան թվերի հետ մինչև թվանշաններ այլևս չմնան։ Այլ կերպ ասած`

  1. Վերցնել ամեն բանալու համար ամենափոքր և էական թվանշանը
  2. Խմբավորել բանալիները այդ թվանշանի հիման վրա, պահպանելով բանալու իրական հիմքը
  3. Կրկնել խմբավորման պրոցեսը ամեն հաջորդ թվանշանի դեպքում

Օրինակ[խմբագրել]

Սկզբնական, չտեսակավորված ցանկ։

170, 45, 75, 90, 802, 24, 2, 66

Տեսակավորում ըստ ամենափոքր տասնավոր թվանշանի։

170, 90, 802, 2, 24, 45, 75, 66

Հարկ է նկատել, որ 802 թիվը կանգնած է 2-ից առաջ, քանի որ սկզբնական տեսքում առկա է այդպիսի դասավորություն։

802, 2, 24, 45, 66, 170, 75, 90

Տեսակավորում ըստ ամենափոքր հարյուրավոր թվանշանի։

2, 24, 45, 66, 75, 90, 170, 802

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

Արտաքին հղումներ[խմբագրել]

Վիքիդարանի պատկերանիշը
Անգլերեն Վիքիդարանում կան նյութեր այս թեմայով՝
Sorting/Radix_sort