Stupid sort Guide, Meaning , Facts, Information and Description
Stupid-sort is probably the simplest known deterministic sort algorithm. It is used for rearranging values in an array to ascending (or descending) order. Its instructional value lies in pointing out how an intuitive, simple algorithm can have a catastrophically low performance in terms of execution time and memory usage.Stupid-sort, however, is not a bogus algorithm per se. (It should not be confused with for example bogosort, which is, if such a thing could be possible, even dumber than stupid-sort.)
Stupid-sort never fails to arrange the data and in the best case (data already in order) it has linear execution time (i.e., its best case execution time is Ω(n)). Additionally, the non-recursive form arranges the data in-place, meaning that no extra memory for temporarily storing the data needs to be allocated.
Unlike bubble sort, this sort algorithm starts all over again if there is a wrong order at all. While this simplifies the algorithm a bit, this also leads to a poor runtime performance.
The small code size and memory footprint of the non-recursive stupid-sort actually makes it quite usable in systems with limited code and data space, for example microcontroller systems.
Stupid-sort is a stable sorting algorithm meaning that two values having the same value always stay in the same order.
| Table of contents |
|
2 The recursive stupid-sort algorithm 3 Memory usage 4 Variants 5 Example source codes |
Quick empiric analysis of the algorithm (see source code below) shows that the number of iterations is a little more than n2 with small values of n. As shown below, if n = 6, the maximum number of iterations needed is 40 (62 = 36).
However, an array of 1024 items needs 178,957,823 iterations of the iterative stupid-sort, which is n2.742. As the number of items grows, the exponent gets closer to 3.
Because the recursion occurs inside the for loop and thus is not tail recursion, it cannot be optimized away by the compiler.
A quick study of the algorithm suggests that in the worst case it reaches n times n recursion levels leading to O(n × n), or, O(n2), extra memory usage for the recursion stack, quickly leading to stack overflow problems even with today's computers.
Note: Since not all instances of the recursion need to be resident at the same time, the O value might also actually be somewhat less than n2. Further study of the subject is required.
It is simple to produce an O(n2) sort from stupid sort by avoiding starting from the beginning after each swap, instead starting from directly before the swapped elements, knowing that the preceding elements are all still in order. The resulting sort is a simple sort with no nested loops called gnome sort.
The following printout shows the sorting of an array with 6 items that are in reverse order. Each line is printed when an exchange operation occurs.
The hash mark (#) shows which items are swapped. The number of steps shows how many times the algorithm has restarted.
This version is in-place, so it won't work for immutable types (such as tuples).
The iterative stupid-sort algorithm
The iterative (i.e. non-recursive) Stupid-sort can be described as:Execution time
Stupid-sort has the best case execution time of O(n) when the data are already in correct order. The worst-case execution time is O(n3) when the data are completely in the wrong order.The recursive stupid-sort algorithm
With recursion, stupid-sort can be made even more stupid than the iterative (non-recursive) form is. Recursive stupid-sort can be expressed as: function stupidSort(array) {
for i from 1 to length(array) - 1
if array[i + 1] < array[i] then {
swap(array[i], array[i + 1])
stupidSort(array)
}
}Execution time
The execution time of the recursive form is still Ω(n) .. O(n3) but the recursion calls add overhead so the recursive form is slower than the iterative form.
Additionally, each recursion level must traverse through the entire array even if the array is already sorted for the recursion to end.
This adds to the overall stupidity of the algorithm.Memory usage
The iterative stupid-sort is not stupid in terms of memory usage since it sorts the array in-place. The memory usage of the recursive version more than makes up for this lack of stupidity.Variants
Example source codes
Pascal source code for iterative stupid-sort
procedure stupidsort (var a: array of integer);
var i: integer;
begin
i := 0;
repeat
inc (i);
if (a[i+1] < a[i]) then begin
exchange (a[i], a[i+1]);
i:=0;
end;
until i = length(A) - 2;
end;The "exchange" function needed by the algorithm might be: procedure exchange (var i, j: integer);
var temp: integer;
begin
temp := i;
i := j;
j := temp;
end;
Example run of the iterative algorithm
6 5 4 3 2 1 initial order
6#5 4 3 2 1 (1 step)
5 6#4 3 2 1 (3 steps)
5#4 6 3 2 1 (4 steps)
4 5 6#3 2 1 (7 steps)
4 5#3 6 2 1 (9 steps)
4#3 5 6 2 1 (10 steps)
3 4 5 6#2 1 (14 steps)
3 4 5#2 6 1 (17 steps)
3 4#2 5 6 1 (19 steps)
3#2 4 5 6 1 (20 steps)
2 3 4 5 6#1 (25 steps)
2 3 4 5#1 6 (29 steps)
2 3 4#1 5 6 (32 steps)
2 3#1 4 5 6 (34 steps)
2#1 3 4 5 6 (35 steps)
1 2 3 4 5 6 final order, total 40 steps.
Python source code for the iterative stupid-sort (in-place)
def stupid_sort(a):
i = 0
while i < len(a) - 1:
if a[i] > a[i + 1]:
a[i], a[i + 1] = a[i + 1], a[i]
i = 0
continue
i += 1