Stupid sort
|
|
Stupid-sort is probably the simplest known deterministic sorting 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.
According to the Jargon file, stupid-sort is a synonym for bogo-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), where n is the number of elements in the array). 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.
| Contents |
The iterative stupid-sort algorithm
The iterative (i.e. non-recursive) Stupid-sort can be described as:
- Starting from start of the array, scan until two succeeding items that are in wrong order are found.
- Swap those items and restart the algorithm (go to line 1).
- The algorithm ends when the end of the array is reached.
function stupidSort(array) {
i := 1
while i < length(array)
if array[i + 1] < array[i] then {
swap(array[i], array[i + 1])
i:=1
} else
i:=i+1
}
Execution time
Stupid-sort has a best case execution time of O(n), which occurs when the array's elements are already in correct order. The worst-case execution time occurs when the elements are in reverse order. In this case, the algorithm will perform <math>(n^3-n)/6 + (n-1)<math> comparisons, resulting in O(n3) performance. For example, the iterative stupid-sort would require 178,957,823 comparisons to sort an array of 1024 items whose elements were initially in reverse order.
...
The recursive stupid-sort algorithm
With recursion, stupid-sort can be made even more stupid than the iterative (non-recursive) form. 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, the algorithm does not end until every recursion level has traversed the entire array, even if the array is already sorted, thus needlessly adding to the number of comparisons performed.
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.
Because the recursion occurs inside the for loop and thus is not tail recursion, it cannot be optimized away by the compiler. In the worst case of elements initially in reverse order, <math>(n^2+n)/2<math> exchanges must be made during the sorting process. Since every exchange is followed by a recursive call, the memory usage of the recursion stack is O(n2), which can easily lead to stack overflow problems even with today's computers.
Variants
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.
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
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.
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)
This version is in-place, so it won't work for immutable types (such as tuples).
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
Python source code for the iterative stupid-sort (not in-place)
This version is not in-place, but works for immutable types (such as tuples).
def ssort(iterable):
"""A simple iterative stupid-sort implementation in python"""
seq = list(iterable)
seqLen = len(seq)
if seqLen <= 1:
return seq
sorted = False
while not sorted:
for index in range(seqLen):
try:
if seq[index] > seq[index+1]:
seq[index], seq[index+1] = seq[index+1], seq[index]
break
except IndexError:
sorted = True
break
return seq
Pascal source code for the recursive stupid-sort
procedure stupidsort (var a:array of integer);
var i:integer;
begin
for i:=1 to length(A)-1 do begin
if a[i+1]<a[i] then begin
exchange (a[i+1],a[i]);
stupidsort(a);
end;
end;
end;