FLUKE?

From: Fred Cisin <cisin_at_xenosoft.com>
Date: Mon Dec 3 17:27:44 2001

On Mon, 3 Dec 2001, Tony Duell wrote:
> 'Bubble Sort' has nothing to do with bubble memory. Bubble sort is a
> well-known, very poor, sorting algorithm -- so poor that one book I have
> contains the quote (from memory) 'If you know what a bubble sort is, wipe
> it from your mind. If you don't, make a point of never finding out' :-)
> The basic algorithm is :
> 1) Compare items 1 and 2 on the list. If they're the wrong way round,
> swap them.
> 2) Now compare items 2 and 3 (of course item 2 might have been item 1 a
> bit ago). Again swap them if they're the wrong way round
> 3) Keep on doing that for items k,k+1 until you've compared (and if
> necesssary swapped) items n-1, n (where n is the size of the list to sort)

You can cut 50% off by:
In each pass, compare first and second, second and third, etc ... up to
comparison of item N - number of passes.

> 4) Now go back and do it again. Always comparing each item with the next
> one. And only ever swapping an item with the next one
> 5) Keep on going through the list until you have a pass where no items
> got swapped. The list is then sorted.

It worst case situation, you can save one pass by stopping when you've
done N-1 passes, even if that last pass did have a swap.
Received on Mon Dec 03 2001 - 17:27:44 GMT