Stooge sort is a
recursive
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
sorting algorithm
In computer science, a sorting algorithm is an algorithm that puts elements of a List (computing), list into an Total order, order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. ...
. It is notable for its exceptionally bad
time complexity
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
of .
The running time of the algorithm is thus slower compared to reasonable sorting algorithms, and is slower than
bubble sort
Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the input list element by element, comparing the current element with the one after it, swapping their values if needed. These passes ...
, a canonical example of a fairly inefficient sort. It is however more efficient than
Slowsort
Slowsort is a sorting algorithm. It is of humorous nature and not useful. It is a ''reluctant algorithm'' based on the principle of ''multiply and surrender'' (a parody formed by taking the opposites of '' divide and conquer''). It was published i ...
. The name comes from
The Three Stooges
The Three Stooges were an American vaudeville and comedy team active from 1922 until 1970, best remembered for their 190 short subject films by Columbia Pictures. Their hallmark styles were physical farce and slapstick. Six Stooges appeared ...
.
The algorithm is defined as follows:
* If the value at the start is larger than the value at the end, swap them.
* If there are 3 or more elements in the list, then:
** Stooge sort the initial 2/3 of the list
** Stooge sort the final 2/3 of the list
** Stooge sort the initial 2/3 of the list again
It is important to get the integer sort size used in the recursive calls by rounding the 2/3 ''upwards'', e.g. rounding 2/3 of 5 should give 4 rather than 3, as otherwise the sort can fail on certain data.
Implementation
function stoogesort(array L, i = 0, j = length(L)-1)
-- Not the best but equal to above
stoogesort :: (Ord a) => -> stoogesort [] = []
stoogesort src = innerStoogesort src 0 ((length src) - 1)
innerStoogesort :: (Ord a) => -> Int -> Int -> 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) => -> Int -> Int -> swap src i j
, a > b = replaceAt (replaceAt src j a) i b
, otherwise = src
where
a = src !! i
b = src !! j
replaceAt :: -> Int -> a -> replaceAt (x:xs) index value
, index 0 = value : xs
, otherwise = x : replaceAt xs (index - 1) value
References
Sources
*
*
External links
Sorting Algorithms (including Stooge sort)
Sorting algorithms
Comparison sorts
Articles with example pseudocode
{{comp-sci-stub