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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
مرتب‌سازی کتابخانه‌ای
کلاس الگوریتم مرتب‌سازی
ساختمان داده‌ها آرایه
عملکرد بدترین حالت O(n^2)
عملکرد بهترین حالت O(n)
عملکرد حالت متوسط O(n\log n)
پیچیدگی فضایی بدترین حالت O(n)

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

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

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

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

پیچیدگی زمانی[ویرایش]

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

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

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

منابع[ویرایش]

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

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