Bogosort

by Lewis Wright: U6 Age ~17

Introduction

This short Pascal implementation of bogosort by Lewis is very different from the complexity of his Battleships game. Bogosort is a method of sorting by which permutations of the values are selected at random until they are in order! The name bogosort is thought to be derived from bogus sort. For n values in a list, there is a 1 in n! chance of selecting the required permutation at each attempt. By gradually increasing the value of the constant MAX in program bogosort, you can experience the progression of factorials. Bogosort is quick enough on modern computers to be usable (if not recommended) for very small values of n, but is likely to take over a minute for n = 12 even when the output of permutations to the screen is suppressed: Output

We could find no reference to bogosort in the 391 pages of the Sorting chapter of Donald Knuth's widely-quoted book, The Art of Computer Programming. We were surprised to find such an in-depth analysis in the wonderfully titled paper by H. Gruber, M Holzer and O. Ruepp: Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms.

The Program

program Bogosort;
{

use this file except in compliance with the License, as described at
}
{\$APPTYPE CONSOLE}
{\$DEFINE OUTPUT}//Comment out to suppress output of permutations
uses
SysUtils;
const
MAX = 5;
var
list, list2 : array[1 .. MAX] of integer;
count, newplace, totalrandoms : integer;
hmm, done : boolean;

function inorder : boolean;
var
count : integer;
begin
inorder := true;
for count := 1 to MAX -1 do
begin
if list[count] > list[count + 1] then
begin
inorder := false;
end;
end;
end;

procedure randomit;
var
count : integer;
begin
for count := 1 to MAX do
begin
repeat
done := false;
newplace := random(MAX) + 1;
if list2[newplace] = 0 then
begin
list2[newplace] := list[count];
done := true;
end;
until done = true;
end;
list := list2;
for count := 1 to MAX do
begin
list2[count] := 0;
end;
end;

begin
totalrandoms := 0;
randomize;
for count := 1 to MAX do
begin
list[count] := random(50000);
end;
writeln('Starting order');
for Count := 1 to MAX do
write(List[count] : 6);
writeln;
writeln('Randomising if necessary');
repeat
hmm := true;
if inorder = false then
begin
hmm := false;
randomit;
{\$IFDEF OUTPUT}
for Count := 1 to MAX do
write(List[Count]:6);
writeln;
{\$ENDIF}
inc(totalrandoms);
end;
until hmm = true;

if inorder = true then
begin
writeln;
writeln('Total number of randomits: ', totalrandoms);
beep;