Գրադարանային տեսակավորում | |
---|---|
Տեսակ | տեսակավորման ալգորիթմ և կայուն տեսակավորման ալգորիթմ |
Տվյալների կառուցվածք | |
Վատագույն դեպքում կատարումը | |
Լավագույն դեպքում կատարումը | |
Օգտագործում է | զանգված |
Գրադարանային տեսակավորում, կամ բացատավորված մուտքային տեսակավորում դա տեսակավորման ալգորիթմ է, որը օգտագործում է մուտքային տեսակավորում, բայց, որը ունի անցում մասսիվում, որպեսզի արագացնի հետագա մուտքերը։ Անունը գալիս է հետևյալ նմանությունից[1]։
Թող, որ գրադարանավարը դասավորի գրքերը այբբենական կարգով՝ երկար դարակում, սկսելով Ա-ից ձախ անկյունից, շարունակելով մինչև դարակի աջ մասը, մինչև Ֆ գրքերի վերջանալը։ Եթե գրադարանավարը ձեռք բերի նոր գիրք, որը պատկանում է Բ սեկցիային, ապա նա պետք է գտնի ճիշտ տեղը Բ սեկցիայում և ստիպված է տեղաշարժել բոլոր գրքերը Բ գրքերի մեջտեղից, որպեսզի տեղ ազատի նոր գրքի համար։ Սա հենց մուտքային տեսակավորումն է։ Սակայն, եթե նա ստիպված է ամեն տառից հետո տեղ թողնել, քանի դեռ տեղ կա Բ-ից հետո, ապա նա ընդամենը մի քանի գիրք պետք է տեղաշարժի, որպեսզի տեղ ազատի նորի համար։ Սա գրադարանային տեսակավորման հիմնական նշանակությունն է։
Ալգորիթմը առաջարկվել է Միքայել Ա. Բենդերի, Մարտին Ֆարահ-Կոլտոնի, և Միգել Մոստեիրոյի կողմից 2006 թ.-ին[2]։
Ներդրումային տեսակավորման նման սա հիմնավորված է, որ գրադարանային տեսակավորումը դա ստաբիլ տարբերվող տեսակավորում է և կարող է աշխատել, որպես առցանց ալգորիթմ; ինչևիցե, արդեն ցույց է տրվել, որ մեծ հաճախությունը աշխատում է O(n log n) ժամանակում (համապատասխանում է արագ տեսակավորմանը), ավելի լավ քան O(n2) ներդրումային տեսակավորումները։ Սրա իրագործումը շատ նման է ցույց տալ էջին։ Գրադարանի օգտագործման թերությունը այն է, որ խլում է ավելորդ տարածք անցումի համար։
{{cite journal}}
: CS1 սպաս․ բազմաթիվ անուններ: authors list (link)
|