مرتب‌سازی کند

برای "مرتب‌سازی ساختگی" که به "مرتب‌سازی کند" نیز شناخته می‌شود، مرتب‌سازی ساختگی را ببینید.

مرتب‌سازی کند (به انگلیسی: Slowsort) نوعی الگوریتم مرتب‌سازی است که جنبهٔ شوخی داشته و کاربردی نمی‌باشد. این الگوریتم بر مبنای قاعده ضرب و تسلیم (کنایه به تقسیم و غلبه) عمل می‌کند. این الگوریتم در سال ۱۹۸۶ توسط آندره برودر و جورج استولفی ابداع شد.^[۱]

الگوریتم

مرتب‌سازی کند یک الگوریتم بازگشتی است.

شبه کد پیاده‌سازی درجای آن به صورت زیر می‌باشد:

 procedure slowsort(A,i,j)
 if i>= j then return
 m := ⌊(i+j)/2⌋
 slowsort(A,i,m)                                    // (1.1)
 slowsort(A,m+1,j)                                  // (1.2)
 if A[j] <A[m] then swap A[j] and A[m]             // (1.3)
 slowsort(A,i,j-1)                                  // (2)

• مرتب‌سازی قسمت اول به صورت بازگشتی (۱٫۱)
• مرتب‌سازی قسمت دوم به صورت بازگشتی (۲٫۲)
• یافتن بیشینه کل آرایه با استفاده از مقایسه نتایج ۱٫۱ و ۲٫۲ و قرار دادن این عنصر در انتهای آرایه (۱٫۳)
• مرتب‌سازی کل آرایه به جز عنصر بیشینهٔ پیدا شده مرحلهٔ ۱٫۳ به صورت بازگشتی

پیاده‌سازی این الگوریتم در هسکل (یه صورت تابعی خالص) به صورت زیر است.

slowsort :: Ord a => [a] -> [a]

 slowsort xs
 | length xs <= 1 = xs
 | otherwise      = slowsort xsnew ++ [max llast rlast] -- (2)
 where
 l     = slowsort $ take m xs -- (1.1)
 r     = slowsort $ drop m xs -- (1.2)
 llast = last l
 rlast = last r
 xsnew = init l ++ min llast rlast: init r
 m     = fst (divMod (length xs) 2)

پیچیدگی زمانی

زمان اجرای مرتب‌سازی کند برابر با ${\displaystyle T(n)=2T(n/2)+T(n-1)+1}$ می‌باشد؛ بنابراین به ازای هر ${\displaystyle \epsilon >0}$ , ${\displaystyle T(n)}$ از مرتبه زمانی ${\displaystyle \Omega \left(n^{\frac {\log _{2}(n)}{(2+\epsilon )}}\right)}$ for any ${\displaystyle \epsilon >0}$ می‌باشد؛ بنابراین مرتبه زمانی مرتب‌سازی کتد چند جمله ای نیست و حتی در بهترین حالت بدتر از مرتب‌سازی جبابی است.

منابع

1. "CiteSeerX — Pessimal Algorithms and Simplexity Analysis". Citeseerx.ist.psu.edu. Retrieved 2017-07-26.