# 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; { 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?