Կարգային տեսակավորում
Բովանդակություն |
Կարգային տեսակավորում [խմբագրել]
Համակարգչային գիտության մեջ կարգային տեսկավորման ալգորիթմը տեսակավորում է թվերը ըստ կարգերի: Գոյություն ունի տեսակավորման երկու մեթոդ`
- 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 բանալիի միջին երկարությունը:
Բացատրություն [խմբագրել]
Յուրաքանչյուր բանալի պայմանականորեն դրվում է մի ուղղանկյունու մեջ, որը կապված է աջակողմյան ուղղանկյունու արժեքի հետ: Գոյություն ունի ուղղակի կապվածություն թվերի և ուղղանկյան մեջ թվանշանի արժեքի միջև: Պրոցեսը կրկնվում է հարևան թվերի հետ մինչև թվանշաններ այլևս չմնան: Այլ կերպ ասած`
- Վերցնել ամեն բանալիի համար ամենափոքր և էական թվանշանը
- Խմբավորել բանալիները այդ թվանշանի հիման վրա, պահպանելով բանալիի իրական հիմքը
- Կրկնել խմբավորման պրոցեսը ամեն հաջորդ թվանշանի դեպքում
Օրինակ [խմբագրել]
Սկզբնական, չտեսակավորված ցանկ:
- 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
Դիտեք նաև [խմբագրել]
Արտաքին հղումներ [խմբագրել]
- Demonstration and comparison of Radix sort with Bubble sort, Merge sort and Quicksort implemented in JavaScript
- Article about Radix sorting IEEE floating-point numbers with implementation.
- Faster Floating Point Sorting and Multiple Histogramming with implementation in C++
- Pointers to radix sort visualizations
- USort library contains tuned implementations of radix sort for most numerical C types (C99)
- Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.2.5: Sorting by Distribution, pp. 168–179.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 8.3: Radix sort, pp. 170–173.
- BRADSORT v1.50 source code
- Efficient Trie-Based Sorting of Large Sets of Strings, by Ranjan Sinha and Justin Zobel. This paper describes a method of creating tries of buckets which figuratively burst into sub-tries when the buckets hold more than a predetermined capacity of strings, hence the name, "Burstsort".
|
