مرتب سازی کند ( به انگلیسی: 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 < A then swap A and A // ( 1. 3 ) slowsort ( A, i, j - 1 ) // ( 2 ) مرتب سازی قسمت اول به صورت بازگشتی ( ۱٫۱ ) مرتب سازی قسمت دوم به صورت بازگشتی ( ۲٫۲ ) یافتن بیشینه کل آرایه با استفاده از مقایسه نتایج ۱٫۱ و ۲٫۲ و قرار دادن این عنصر در انتهای آرایه ( ۱٫۳ ) مرتب سازی کل آرایه به جز عنصر بیشینهٔ پیدا شده مرحلهٔ ۱٫۳ به صورت بازگشتی پیاده سازی این الگوریتم در هسکل ( یه صورت تابعی خالص ) به صورت زیر است.
slowsort :: Ord a => - >
slowsort xs | length xs < = 1 = xs | otherwise = slowsort xsnew ++ - - ( 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 ) پیچیدگی زمانی زمان اجرای مرتب سازی کند برابر با T ( n ) = 2 T ( n / 2 ) + T ( n − 1 ) + 1 می باشد؛ بنابراین به ازای هر ϵ > 0 , T ( n ) از مرتبه زمانی Ω ( n log 2 ( n ) ( 2 + ϵ ) ) for any ϵ > 0 می باشد؛ بنابراین مرتبه زمانی مرتب سازی کتد چند جمله ای نیست و حتی در بهترین حالت بدتر از مرتب سازی جبابی است.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفمرتب سازی کند یک الگوریتم بازگشتی است.
شبه کد پیاده سازی درجای آن به صورت زیر می باشد:
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 < A then swap A and A // ( 1. 3 ) slowsort ( A, i, j - 1 ) // ( 2 ) مرتب سازی قسمت اول به صورت بازگشتی ( ۱٫۱ ) مرتب سازی قسمت دوم به صورت بازگشتی ( ۲٫۲ ) یافتن بیشینه کل آرایه با استفاده از مقایسه نتایج ۱٫۱ و ۲٫۲ و قرار دادن این عنصر در انتهای آرایه ( ۱٫۳ ) مرتب سازی کل آرایه به جز عنصر بیشینهٔ پیدا شده مرحلهٔ ۱٫۳ به صورت بازگشتی پیاده سازی این الگوریتم در هسکل ( یه صورت تابعی خالص ) به صورت زیر است.
slowsort :: Ord a => - >
slowsort xs | length xs < = 1 = xs | otherwise = slowsort xsnew ++ - - ( 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 ) پیچیدگی زمانی زمان اجرای مرتب سازی کند برابر با T ( n ) = 2 T ( n / 2 ) + T ( n − 1 ) + 1 می باشد؛ بنابراین به ازای هر ϵ > 0 , T ( n ) از مرتبه زمانی Ω ( n log 2 ( n ) ( 2 + ϵ ) ) for any ϵ > 0 می باشد؛ بنابراین مرتبه زمانی مرتب سازی کتد چند جمله ای نیست و حتی در بهترین حالت بدتر از مرتب سازی جبابی است.
wiki: مرتب سازی کند