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