I don’t know if bubble sort using a random number for comparisons
is
always a good idea. Bubble sort runs over the array and compares
two
subsequent values and swaps them if they are out of order.
It keeps doing that until there are no more swaps during a run.
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.)
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.