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

Գրադարանային տեսակավորում
Տեսակ	տեսակավորման ալգորիթմ և կայուն տեսակավորման ալգորիթմ
Տվյալների կառուցվածք	$O(n)$
Վատագույն դեպքում կատարումը	$O(n^{2})$
Լավագույն դեպքում կատարումը	$O(n)$
Օգտագործում է	զանգված

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

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

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

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

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

• Gapped Insertion Sort

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