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

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

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

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

Գրականության ցանկ

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

Տեսակավորման ալգորիթմներ
Տարբերվող տեսակավորում
Կայուն տեսակավորում
Առցանց տեսակավորում