स्टूज सॉर्ट: 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 |
||
Line 10: | Line 10: | ||
|optimal=No | |optimal=No | ||
}} | }} | ||
स्टूज सॉर्ट एक | |||
"स्टूज सॉर्ट" एक रीकर्सिव सॉर्टिंग एल्गोरिदम है। इसकी विशेषता है कि इसका असाधारण खराब समय जटिलता है, जो {{nowrap|1=[[बड़ ओ नोटेशन|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> | |||
एल्गोरिथ्म को इस प्रकार परिभाषित किया गया है: | एल्गोरिथ्म को इस प्रकार परिभाषित किया गया है: | ||
* यदि प्रारंभ में मान अंत में मान से बड़ा है, तो उन्हें स्वैप करें। | * यदि प्रारंभ में मान अंत में मान से बड़ा है, तो उन्हें स्वैप करें। | ||
Line 85: | Line 87: | ||
{{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: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]] |
Revision as of 01:00, 2 August 2023
Class | Sorting algorithm |
---|---|
Data structure | Array |
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.
बाहरी संबंध