From: Peter <Peter.Vanbroekhoven@...>
Date: 2003-09-18T03:30:27+09:00
Subject: Re: Bubble sort and rand()

> No, that's an optimization to end early if there *ARE* no swaps.  The
> sort still just runs through the list a maximum n (or n-1) times. (Or
> at least there's no reason NOT to.)

I guess that depends on how they taught you that in college. We learned
that you do it until there are no more swaps, but you know there's a
maximum of n-1 runs (that's how much the last element needs to move to the
head of the array), and that's why complexity is quadratic. But you are
right, if you do it your way, whatever I said doesn't hold.

Peter