Bogosort

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;
{
    Copyright (c) 2011 Lewis Wright

    Licensed under the Apache License, Version 2.0 (the "License"); you may not
    use this file except in compliance with the License, as described at
    http://www.apache.org/licenses/ and http://www.pp4s.co.uk/licenses/
}
  {$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;
      readln;
    end;
end.

Remarks

How many types of sort can you code?