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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به ناوبری پرش به جستجو
مرتب‌سازی دست‌نشانده
کلاسالگوریتم مرتب‌سازی
ساختمان دادهآرایه
کارایی بدترین حالت
پیچیدگی محاسباتی بدترین حالت
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

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

  • Black, Paul E. "stooge sort". Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. Retrieved 2011-06-18.