Bogosort (was: old threaded languages, was Re: Symbolics)

From: Eric Smith <eric_at_brouhaha.com>
Date: Wed Mar 1 15:13:35 2000

John Wilson <wilson_at_dbit.dbit.com> wrote:
> I remember one of Jerry Pournelle's more lucid rants in Byte, ages ago, where
> he questions the whole point of the Bubble Sort to begin with. Not only
> is it an absolutely horrible algorithm, it's not even immediately obvious
> how it works!

I'd have to disagree with him about the obviousness. It seems perfectly
obvious to me that if you keep swapping out-of-order elements long enough,
eventually a list will be sorted. It also seems obvious that if you do
this systematically by scanning the list from one end to the other
repeatedly, that it can take no more than n-1 passes, the time it would take
an element to move from one end of the list to the other.

The only other in-place sort that seems more obvious to me is:

  for (i = 0; i < (n-1); i++)
    for (j = (i+1); j < n; j++)
      if (a [j] < a [i])
        swap (& a [j], & a [i]);

which has the disadvantage over bubble sort of doing more swaps.

A Shell-Metzner (sp?) sort is substantially more efficient but also much
less obvious.
Received on Wed Mar 01 2000 - 15:13:35 GMT