स्टूज सॉर्ट

From Vigyanwiki
स्टूज सॉर्ट
Sorting stoogesort anim.gif
स्टूज सॉर्ट का एक दृश्यांतरण (केवल स्वैप्स दिखाए गए हैं)।
Classसॉर्टिंग ऐल्गरिदम
Data structure ऐरे
Worst-case performanceO(nlog 3/log 1.5)
Worst-case space complexityO(n)

स्टूज सॉर्ट, एक रीकर्सिव सॉर्टिंग एल्गोरिथ्म है। यह अपनी असाधारण रूप से खराब समय कम्प्लेक्सिटी O(nlog 3 / log 1.5 ) = O(n2.7095...) के लिए उल्लेखनीय है।

इस प्रकार एल्गोरिदम का रनिंग टाइम, कई सॉर्टिंग एल्गोरिदम की तुलना में धीमा है, और बबल सॉर्ट की तुलना में धीमा है, जो अत्यधिक इनएफीसिएंट सॉर्ट का एक विहित उदाहरण है। यद्यपि यह स्लोसॉर्ट से अधिक एफीसिएंट है। यह नाम थ्री स्टूग से आया है।[1]

एल्गोरिथ्म को इस प्रकार परिभाषित किया गया है:

  • यदि प्रारम्भिक मान अंत मान से बड़ा है, तो उन्हें स्वैप करें।
  • यदि सूची में 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


संदर्भ

  1. "CSE 373" (PDF). courses.cs.washington.edu. Retrieved 2020-09-14.



स्रोत

बाहरी संबंध