Monday, March 1, 2010

Art of computer programming -Sorting #5

Improvements that can be made on bubble sort

There are basically 2 improvements that you can make on bubble sort.

One, you can eliminate certain comparisons. For example if 2 elements i and j in an array don't change their respective positions in 2 simultaneous passes during a bubble sort. Then it means that the values are in their final positions. Such elements can be left alone when comparing.

Another distant possibility is that we can shift the base of the array left or right when we want to shift a position to left or right. This will help us in doing lesser number of comparisons. But whatever we do, it does not make the bubble sort any better than a selection sort or an insertion sort.

So layman tells you to quit using the bubble sort for practical purposes.

Thanking you,
Layman