مرتبسازی دستنشانده
مرتبسازی دستنشانده (به انگلیسی: 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.