Stupid sort

Stupid-sort, however, is not a bogus algorithm per se. (It should not be confused with for example bogosort, which is 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), 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.

The iterative stupid-sort algorithm

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.
   

   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 comparisons, resulting in O(n³) 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:

Execution time

Memory usage

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, 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(n²), which can easily lead to stack overflow problems even with today's computers.

Variants

It is simple to produce an O(n²) 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

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

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]