स्टूज सॉर्ट

स्टूज सॉर्ट

Visualization of Stooge sort (only shows swaps).
Class	Sorting algorithm
Data structure	Array
Worst-case performance	O(nlog 3/log 1.5)
Worst-case space complexity	O(n)

स्टूज सॉर्ट एक प्रत्यावर्तन छँटाई एल्गोरिथ्म है। यह अपनी असाधारण रूप से खराब समय जटिलता के लिए उल्लेखनीय है O(n^{log 3 / log 1.5} ) = O(n^2.7095...). इस प्रकार एल्गोरिदम का चलने का समय उचित सॉर्टिंग एल्गोरिदम की तुलना में धीमा है, और बुलबुले की तरह की तुलना में धीमा है, जो काफी अक्षम सॉर्ट का एक विहित उदाहरण है। हालाँकि यह स्लोसॉर्ट से अधिक कुशल है। यह नाम तीन कठपुतलियां से आया है। एल्गोरिथ्म को इस प्रकार परिभाषित किया गया है:

• यदि प्रारंभ में मान अंत में मान से बड़ा है, तो उन्हें स्वैप करें।
• यदि सूची में 3 या अधिक तत्व हैं, तो:
  • स्टूज सूची के प्रारंभिक 2/3 को क्रमबद्ध करें
  • स्टूगे सूची के अंतिम 2/3 को क्रमबद्ध करें
  • स्टूज सूची के प्रारंभिक 2/3 को फिर से क्रमबद्ध करें

पुनरावर्ती कॉल में उपयोग किए जाने वाले पूर्णांक सॉर्ट आकार को 2/3 ऊपर की ओर पूर्णांकित करके प्राप्त करना महत्वपूर्ण है, उदाहरण के लिए 5 में से 2/3 को पूर्णांकित करने पर 3 के बजाय 4 आना चाहिए, अन्यथा कुछ डेटा पर सॉर्ट विफल हो सकता है।

कार्यान्वयन

 function stoogesort(array L, i = 0, j = length(L)-1){
     if L[i] > L[j] then       // If the leftmost element is larger than the rightmost element
         L[i] ↔ L[j]           // Swap the leftmost element and the rightmost element
     if (j - i + 1) > 2 then       // If there are at least 3 elements in the array
         t = floor((j - i + 1) / 3) // Rounding down
         stoogesort(L, i  , j-t)  // Sort the first 2/3 of the array
         stoogesort(L, i+t, j)    // Sort the last 2/3 of the array
         stoogesort(L, i  , j-t)  // Sort the first 2/3 of the array again
     return L
 }

-- Not the best but equal to above 

stoogesort :: (Ord a) => [a] -> [a]
stoogesort [] = []
stoogesort src = innerStoogesort src 0 ((length src) - 1)

innerStoogesort :: (Ord a) => [a] -> Int -> Int -> [a]
innerStoogesort src i j 
    | (j - i + 1) > 2 = src''''
    | otherwise = src'
    where 
        src'    = swap src i j -- need every call
        t = floor (fromIntegral (j - i + 1) / 3.0)
        src''   = innerStoogesort src'   i      (j - t)
        src'''  = innerStoogesort src'' (i + t)  j
        src'''' = innerStoogesort src''' i      (j - t)

swap :: (Ord a) => [a] -> Int -> Int -> [a]
swap src i j 
    | a > b     =  replaceAt (replaceAt src j a) i b
    | otherwise = src
    where 
        a = src !! i
        b = src !! j

replaceAt :: [a] -> Int -> a -> [a]
replaceAt (x:xs) index value
    | index == 0 = value : xs
    | otherwise  =  x : replaceAt xs (index - 1) value

संदर्भ

स्रोत

• Black, Paul E. "कठपुतली प्रकार". Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. Retrieved 18 June 2011.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "Problem 7-3". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 161–162. ISBN 0-262-03293-7.

बाहरी संबंध

• Sorting Algorithms (including Stooge sort)
• Stooge sort – implementation and comparison