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

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

رده	الگوریتم مرتب‌سازی
ساختمان داده	آرایه
کارایی بدترین حالت	$O(n\log n)$
کارایی متوسط	$O(n\log n)$

مرتب‌سازی درونگرا، یک الگوریتم جستجو است که توسط دیوید ماسر (David Musser) در سال ۱۹۹۷ طراحی شد. این الگوریتم ابتدا با فراخوانی مرتب‌سازی سریع شروع کرده و هنگامی بخش بازگشتی مرتب‌سازی سریع به عمق مشخصی که متناسب با لگاریتم تعداد عناصر موجود است رسید، الگوریتم مرتب‌سازی هرمی را فراخوانی می‌کند. این گونه پیاده‌سازی باعث می‌شود که الگوریتم هم سرعت زیاد مرتب‌سازی سریع را روی داده‌های معمولی داشته باشد و هم بدترین زمان اجرای آن $O(nlogn)$ باشد. در الگوریتم مرتب‌سازی سریع یکی از مهم‌ترین مراحل انتخاب نقطه محور (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

منابع

• Musser, David (1997). "Introspective Sorting and Selection Algorithms". Software: Practice and Experience. Wiley. ۲۷ (۸): ۹۸۳–۹۹۳. doi:10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#. Archived from the original on 16 July 2012. Retrieved 9 December 2011.