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

Գրադարանային տեսակավորում
Տեսակ	տեսակավորման ալգորիթմ և կայուն տեսակավորման ալգորիթմ
Տվյալների կառուցվածք
Վատագույն դեպքում կատարումը
Լավագույն դեպքում կատարումը
Օգտագործում է	զանգված

Գրադարանային տեսակավորում, կամ բացատավորված մուտքային տեսակավորում դա տեսակավորման ալգորիթմ է, որը օգտագործում է մուտքային տեսակավորում, բայց, որը ունի անցում մասսիվում, որպեսզի արագացնի հետագա մուտքերը։ Անունը գալիս է հետևյալ նմանությունից^[1]։

Թող, որ գրադարանավարը դասավորի գրքերը այբբենական կարգով՝ երկար դարակում, սկսելով Ա-ից ձախ անկյունից, շարունակելով մինչև դարակի աջ մասը, մինչև Ֆ գրքերի վերջանալը։ Եթե գրադարանավարը ձեռք բերի նոր գիրք, որը պատկանում է Բ սեկցիային, ապա նա պետք է գտնի ճիշտ տեղը Բ սեկցիայում և ստիպված է տեղաշարժել բոլոր գրքերը Բ գրքերի մեջտեղից, որպեսզի տեղ ազատի նոր գրքի համար։ Սա հենց մուտքային տեսակավորումն է։ Սակայն, եթե նա ստիպված է ամեն տառից հետո տեղ թողնել, քանի դեռ տեղ կա Բ-ից հետո, ապա նա ընդամենը մի քանի գիրք պետք է տեղաշարժի, որպեսզի տեղ ազատի նորի համար։ Սա գրադարանային տեսակավորման հիմնական նշանակությունն է։

Ալգորիթմը առաջարկվել է Միքայել Ա. Բենդերի, Մարտին Ֆարահ-Կոլտոնի, և Միգել Մոստեիրոյի կողմից 2006 թ.-ին^[2]։

Ներդրումային տեսակավորման նման սա հիմնավորված է, որ գրադարանային տեսակավորումը դա ստաբիլ տարբերվող տեսակավորում է և կարող է աշխատել, որպես առցանց ալգորիթմ; ինչևիցե, արդեն ցույց է տրվել, որ մեծ հաճախությունը աշխատում է O(n log n) ժամանակում (համապատասխանում է արագ տեսակավորմանը), ավելի լավ քան O(n²) ներդրումային տեսակավորումները։ Սրա իրագործումը շատ նման է ցույց տալ էջին։ Գրադարանի օգտագործման թերությունը այն է, որ խլում է ավելորդ տարածք անցումի համար։

Գրականության ցանկ խմբագրել

↑ Budd, Timothy A., An Active Learning approach to Data Structures using C (PDF), Արխիվացված է օրիգինալից (PDF) 2011 թ․ հուլիսի 20-ին, Վերցված է 2011 թ․ մայիսի 18-ին
↑ Bender, M. A., Farach-Colton, M., and Mosteiro M. (2006). «Insertion Sort is O(n log n)». Theory of Computing Systems. 39 (3): 391. doi:10.1007/s00224-005-1237-z.{{cite journal}}: CS1 սպաս․ բազմաթիվ անուններ: authors list (link)

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

Gapped Insertion Sort

Կաղապար:Comp-sci-stub

[1] Budd, Timothy A., An Active Learning approach to Data Structures using C (PDF), Արխիվացված է օրիգինալից (PDF) 2011 թ․ հուլիսի 20-ին, Վերցված է 2011 թ․ մայիսի 18-ին

[2] Bender, M. A., Farach-Colton, M., and Mosteiro M. (2006). «Insertion Sort is O(n log n)». Theory of Computing Systems. 39 (3): 391. doi:10.1007/s00224-005-1237-z.{{cite journal}}: CS1 սպաս․ բազմաթիվ անուններ: authors list (link)

[1]

[2]