1 Mar
2000
1 Mar
'00
7:13 a.m.
John Wilson <wilson(a)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.