स्टूज सॉर्ट

स्टूज सॉर्ट

स्टूज सॉर्ट का एक दृश्यांतरण (केवल स्वैप्स दिखाए गए हैं)।
Class	सॉर्टिंग ऐल्गरिदम
Data structure	ऐरे
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