مرتب‌سازی کتابخانه‌ای

مرتب‌سازی کتابخانه‌ای

رده	الگوریتم مرتب‌سازی
ساختمان داده	آرایه
کارایی بدترین حالت	${\displaystyle O(n^{2})}$
کارایی بهترین حالت	${\displaystyle O(n)}$
کارایی متوسط	${\displaystyle O(n\log n)}$
پیچیدگی فضایی	${\displaystyle O(n)}$

مرتب‌سازی کتابخانه‌ای یا مرتب‌سازی درجی شکافدار یک الگوریتم مرتب‌سازی است که ازمرتب‌سازی درجی به همراه فضاهای خالی یا همان شکاف‌ها برای سرعت دادن به فرایند درج یک زیر رشته جدید استفاده می‌کند.^[۱]

فرض کنید یک کتابدار می‌خواهد کتابهایش را بر حسب حروف الفبا در یک قفسه بچیند، به طوری که از حرف الف در سمت چپ شروع می‌کند به چیدن و به سمت راست می‌رود تا به حرف ی برسد و در بین حروف هم هیچ فاصله‌ای نمی‌گذارد. اگر کتابدار یک کتاب جدید را که باحرف ب شروع می‌شود را بخواهد در قفسه بگذارد باید اول جای ان را پیدا کند و سپس همه کتابها را از انجا به بعد یکی جلو ببرد تا جا برای کتاب باز شود، ای دقیقاً همان کاری است که در مرتب‌سازی درجی انجام می‌دهیم. اگر ما یک فاصله بعد از هر حرف می‌گذاشتیم نیازی نبود که همهٔ کتاب‌ها را جلو ببریم و فقط تعداد کمی کتاب را جابجا می‌کردیم که این ایدهٔ فضای خالی گذاشتن مهمترین اصل مرتب‌سازی کتابخانه‌ای است.

این الگوریتم به وسیلهٔ Michael A. Bender، Martín Farach-Colton و Miguel Mosteiro در سال ۲۰۰۶ معرفی شد.

مثل مرتب‌سازی درجی که به عنوان پایه مرتب‌سازی کتابخانه‌ای است، این نوع مرتب‌سازی از نوع مرتب‌سازی‌های مقایسه‌ای پایدار است و می‌تواند به عنوان یک الگوریتم(online)اجرا شود یعنی نیازی نیست که همهٔ داده‌ها به ان داده شوند تا کار کند بلکه می‌تواند از لحظهٔ وارد شدن داده‌ها کار مرتب‌سازی داده‌ها را انجام بدهد. ازمایشات نشان داده که احتمال اجرای این الگوریتم با پیچیدگی زمانی (o(nlogn بیشتراز (quicksort) است. پیاده‌سازی این نوع الگوریتم بسیار شبیه لیست پرشی است. تنها مشکل این نوع مرتب‌سازی استفاده زیاد از حافظه برای ایجاد شکاف‌ها است.

بدترین پیچیدگی (o(n^2

بهترین پیچیدگی (o(n

پیچیدگی متوسط (o(nlogn

مرتب‌سازی شکافدار