Why aren't we all speaking LISP now?

[Christian Tanzer]

Roy Smith <roy at panix.com> wrote:

> All that being said, bubble sort is actually a decent algorithm to use
> if you know ahead of time that the data is already almost completely
> sorted. For example, let's say I had a list of the batting averages of
> all the major league baseball players. These don't change much from
> day to day (at least past the first few weeks of the season). If I
> updated each player's stats to include today's games, and wanted to
> re-sort the list in order of batting average, bubble sort might be a
> reasonable algorithm to pick.

That's a myth. There are only two cases of almost sorted data where
bubble sort is better than straight insert sort:

- completely sorted data

- the biggest element is in a random position

In all other cases of almost sorted data, bubble sort is a dog. For
instance, if you put a random element at the the of the data or if you
swap pairs of elements of an already sorted array, bubble sort behaves
as O(n**2).

OTOH, straight insert sort behaves like O(n) for almost sorted data.

In other words, bubble sort might be the best algorithm for two
marginal cases, but if you don't know that your data always behave
like that, it is a *bad* choice. 

-- 
Christian Tanzer                                         tanzer at swing.co.at
Glasauergasse 32                                       Tel: +43 1 876 62 36
A-1130 Vienna, Austria                                 Fax: +43 1 877 66 92