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

Կարգային տեսակավորում
Տեսակ	տեսակավորման ալգորիթմ
Տվյալների կառուցվածք	$O(w+n)$
Վատագույն դեպքում կատարումը	$O(w\cdot n)$
Օգտագործում է	զանգված
Հայտնաբերող	Հերման Հոլերիթ

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

• 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

Դիտեք նաև

• IBM 80 series Card Sorters
• Spaghetti sort

Արտաքին հղումներ

• 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 Արխիվացված 2006-08-29 Wayback Machine
• USort library Արխիվացված 2011-08-07 Wayback Machine 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 Արխիվացված 2012-02-08 Wayback Machine, 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".