Stupid sort



         


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.

[Top]

The iterative stupid-sort algorithm

The iterative (i.e. non-recursive) Stupid-sort can be described as:

  1. Starting from start of the array, scan until two succeeding items that are in wrong order, are found.
  2. Swap those items and restart the algorithm (go to line 1).
  3. The algorithm ends when the end of the array is reached.
[Top]

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.

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.

[Top]

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:

procedure STUPID-SORT (array A) is: 1 for i := 1 to length(A) - 1 do 2 if A[i+1] < A[i] then 3 exchange (A[i], A[i+1]) 4 STUPID-SORT (A) 5 endif 6 endfor
[Top]

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.


[Top]

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. 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.

[Top]

Example source codes

[Top]

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;
[Top]

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.
[Top]

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
[Top]

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
[Top]

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;






  View Live Article   This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License