3 Dec
2001
3 Dec
'01
9:27 a.m.
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.