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

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

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

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

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

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

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

  1. Budd, Timothy A., An Active Learning approach to Data Structures using C, http://classes.engr.oregonstate.edu/eecs/winter2009/cs261/Textbook/Chapter14.pdf 
  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. 

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

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