مرتب‌سازی دست‌نشانده

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
مرتب‌سازی دست‌نشانده
Sorting stoogesort anim.gif
تجسم مرتب‌سازی دست‌نشانده.
کلاس الگوریتم مرتب‌سازی
ساختمان داده‌ها آرایه
عملکرد بدترین حالت O(n^{\log 3 / \log 1.5})
پیچیدگی فضایی بدترین حالت O(n)

مرتب‌سازی دست‌نشانده (به انگلیسی: Stooge sort) یک الگوریتم مرتب‌سازی بازگشتی با پیچیدگی زمانی O(n^{log 3 / log 1.5}) = O(n^{2.7095...}) است؛ بنابراین زمان اجرای الگوریتم در مقایسه با الگوریتم‌های مرتب‌سازی کارآمد، مانند مرتب‌سازی ادغامی، بسیار آهسته بوده و حتی آهسته‌تر از مرتب‌سازی حبابی عمل می‌کند.

این الگوریتم نامش را از کمدی بزن و بکوب سه دست‌نشانده گرفته‌است، که یکی از دست‌نشانده‌ها دو دست‌نشانده دیگر را کتک می‌زند.[نیازمند منبع]

پیاده‌سازی[ویرایش]

 function stoogesort(array L, i = 0, j = length(L)-1)
     if L[j] < L[i] then
         L[i] ↔ L[j]
     if (j - i + 1) >= 3 then
         t = (j - i + 1) / 3
         stoogesort(L, i  , j-t)
         stoogesort(L, i+t, j)
         stoogesort(L, i  , j-t)
     return L

پانویس[ویرایش]