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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به ناوبری پرش به جستجو
مرتب‌سازی دست‌نشانده
Sorting stoogesort anim.gif
تجسم مرتب‌سازی دست‌نشانده.
کلاس الگوریتم مرتب‌سازی
ساختمان داده‌ها آرایه
عملکرد بدترین حالت
پیچیدگی فضایی بدترین حالت

مرتب‌سازی دست‌نشانده (به انگلیسی: Stooge sort) یک الگوریتم مرتب‌سازی بازگشتی با پیچیدگی زمانی است؛ بنابراین زمان اجرای الگوریتم در مقایسه با الگوریتم‌های مرتب‌سازی کارآمد، مانند مرتب‌سازی ادغامی، بسیار آهسته بوده و حتی آهسته‌تر از مرتب‌سازی حبابی عمل می‌کند.

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

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

 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

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