स्टूज सॉर्ट: Difference between revisions
From Vigyanwiki
(Created page with "{{short description|Inefficient recursive sorting algorithm}} {{Use dmy dates|date=September 2020}} {{Infobox Algorithm |image = File:Sorting stoogesort anim.gif |caption...") |
No edit summary |
||
(6 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
{{short description|Inefficient recursive sorting algorithm}} | {{short description|Inefficient recursive sorting algorithm}} | ||
{{Infobox Algorithm | {{Infobox Algorithm | ||
|image = [[File:Sorting stoogesort anim.gif]] | |image = [[File:Sorting stoogesort anim.gif]] | ||
|caption = | |caption = स्टूज सॉर्ट का एक दृश्यांतरण (केवल स्वैप्स दिखाए गए हैं)। | ||
|class=[[ | |class=[[सॉर्टिंग ऐल्गरिदम]] | ||
|data=[[ | |data=[[ऐरे डेटा स्ट्रक्चर| ऐरे]] | ||
|time = {{nowrap|1=O(''n''<sup>log 3/log 1.5</sup>)}} | |time = {{nowrap|1=O(''n''<sup>log 3/log 1.5</sup>)}} | ||
|space = O(''n'') | |space = O(''n'') | ||
|optimal=No | |optimal=No | ||
}} | }} | ||
स्टूज सॉर्ट एक | |||
इस प्रकार एल्गोरिदम का | '''स्टूज सॉर्ट,''' एक [[छँटाई एल्गोरिथ्म|रीकर्सिव सॉर्टिंग एल्गोरिथ्म]] है। यह अपनी असाधारण रूप से खराब समय कम्प्लेक्सिटी {{nowrap|1=[[Big O notation|O]](''n''<sup>log 3 / log 1.5 </sup>) = O(''n''<sup>2.7095...</sup>)}} के लिए उल्लेखनीय है। | ||
इस प्रकार एल्गोरिदम का रनिंग टाइम, कई सॉर्टिंग एल्गोरिदम की तुलना में धीमा है, और [[ बुलबुले की तरह | बबल सॉर्ट]] की तुलना में धीमा है, जो अत्यधिक इनएफीसिएंट सॉर्ट का एक विहित उदाहरण है। यद्यपि यह [[स्लोसॉर्ट]] से अधिक एफीसिएंट है। यह नाम [[तीन कठपुतलियां|थ्री स्टूग]] से आया है।<ref>{{cite web |url=https://courses.cs.washington.edu/courses/cse373/13wi/lectures/02-22/18-sorting1-bogo-stooge-bubble.pdf |title= CSE 373 |website= courses.cs.washington.edu|format=PDF|access-date=2020-09-14}}</ref> | |||
एल्गोरिथ्म को इस प्रकार परिभाषित किया गया है: | एल्गोरिथ्म को इस प्रकार परिभाषित किया गया है: | ||
* यदि | * यदि प्रारम्भिक मान अंत मान से बड़ा है, तो उन्हें स्वैप करें। | ||
* यदि सूची में 3 या अधिक तत्व हैं, तो: | * यदि सूची में 3 या अधिक तत्व हैं, तो: | ||
** | **सूची के प्रारंभिक 2/3 को स्टूज सॉर्ट करें | ||
** | **सूची के अंतिम 2/3 को स्टूज सॉर्ट करें | ||
** | **सूची के प्रारंभिक 2/3 को पुनः स्टूज सॉर्ट करें | ||
[[छँटाई एल्गोरिथ्म|रीकर्सिव]] कॉल में उपयोग किए जाने वाले इन्टिजर सॉर्ट आकार को 2/3 "अपवर्ड" राउन्ड करके प्राप्त करना महत्वपूर्ण है, उदाहरण के लिए 5 में से 2/3 को पूर्णांकित करने पर 3 के अतिरिक्त 4 आना चाहिए, अन्यथा कुछ डेटा पर सॉर्ट विफल हो सकता है। | |||
==कार्यान्वयन== | ==कार्यान्वयन== | ||
Line 85: | Line 88: | ||
{{sorting}} | {{sorting}} | ||
{{DEFAULTSORT:Stooge Sort}} | {{DEFAULTSORT:Stooge Sort}} | ||
{{comp-sci-stub}} | {{comp-sci-stub}} | ||
[[Category:All stub articles|Stooge Sort]] | |||
[[Category:Articles with invalid date parameter in template|Stooge Sort]] | |||
[[Category: | [[Category:Collapse templates|Stooge Sort]] | ||
[[Category:Created On 26/07/2023]] | [[Category:Computer science stubs|Stooge Sort]] | ||
[[Category:Created On 26/07/2023|Stooge Sort]] | |||
[[Category:Lua-based templates|Stooge Sort]] | |||
[[Category:Machine Translated Page|Stooge Sort]] | |||
[[Category:Navigational boxes| ]] | |||
[[Category:Navigational boxes without horizontal lists|Stooge Sort]] | |||
[[Category:Pages with script errors|Stooge Sort]] | |||
[[Category:Short description with empty Wikidata description|Stooge Sort]] | |||
[[Category:Sidebars with styles needing conversion|Stooge Sort]] | |||
[[Category:Template documentation pages|Documentation/doc]] | |||
[[Category:Templates Vigyan Ready|Stooge Sort]] | |||
[[Category:Templates generating microformats|Stooge Sort]] | |||
[[Category:Templates that add a tracking category|Stooge Sort]] | |||
[[Category:Templates that are not mobile friendly|Stooge Sort]] | |||
[[Category:Templates that generate short descriptions|Stooge Sort]] | |||
[[Category:Templates using TemplateData|Stooge Sort]] | |||
[[Category:Wikipedia metatemplates|Stooge Sort]] |
Latest revision as of 14:43, 11 August 2023
Class | सॉर्टिंग ऐल्गरिदम |
---|---|
Data structure | ऐरे |
Worst-case performance | O(nlog 3/log 1.5) |
Worst-case space complexity | O(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
संदर्भ
स्रोत
- 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.
बाहरी संबंध