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

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

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

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

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

پیچیدگی زمانی

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

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

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

مطالعهٔ بیشتر

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