مرتب‌سازی درونگرا

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

مرتب سازی درونگرا، یک الگوریتم جستجو است که توسط دیوید ماسر (David Musser) در سال ۱۹۹۷ طراحی شد. این الگوریتم ابتدا با فراخوانی مرتب سازی سریع شروع کرده و هنگامی بخش بازگشتی مرتب سازی سریع به عمق مشخصی که متناسب با لگاریتم تعداد عناصر موجود است رسید، الگوریتم مرتب سازی هرمی را فراخوانی می کند. این گونه پیاده سازی باعث می شود که الگوریتم هم سرعت زیاد مرتب سازی سریع را روی داده های معمولی داشته باشد و هم بدترین زمان اجرای آن O(n log n) باشد. در الگوریتم مرتب سازی سریع یکی از مهمترین مراحل انتخاب نقطه محور (Pivot Element) می باشد که عناصر درون آرایه حول آن بخش بندی می شوند. ساده ترین الگوریتم انتخاب نقطه محور، انتخاب اولین یا آخرین عنصر آرایه است که باعث می شود الگوریتم برای آرایه های مرتب زمان اجرای بدی داشته باشد. الگوریتم های دیگری نیز مانند میانه ۳ (median-of-۳) وجود دارند، اما آنها هم در بدترین حالت زمان اجرای (O(n² خواهند داشت. این نوع ورودی ها می توانند هنگام حمله های انکار سرویس در اینترنت به کار روند. شبه کد الگوریتم با بخش بندی میانه ۳ به صورت زیر می باشد:

Algorithm Introsort(A, f, b)
       A: Input array  A[f]… A[b - 1]
       f: The first Position of sequence
       b: The first position beyond the end of sequence
 
      Introsort_Loop(A, f, b, 2 * log(b – f))
      InsertionSort(A, f, b)
 
Algorithm Introsort_Loop(A, f, b, depth_limit)
   while b – f > size_threshold
      do if depth_limit = 0
           then HeapSort(A, f, b)
                  return
      depth_limit = depth_limit – 1
      p = Partiotion(A, f, b, MedianOf3(A[f], A[f + (b – f)/2], A[b – 1]))
      Introsort_Loop(A, p, b, depth_limit)
      b = p

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