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

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

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

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

  • 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