Sorted arrays and bubble sort

Sorted lists

Sorted arrays

There can be a total ordering on elements in a array.

We want to return an array such that only the ordering is changed.

\(\forall nm [array[n]>array[m] \leftrightarrow n>m]\)

Checking if an array is sorted

Checking a sortable array

Bubble sort

Bubble sort

Take the first two items. See if they are sorted. If they are not, swap them.

Then move to next pair, and do same.

Keep going until the end.

If the number of swaps was greater than 0, loop around again.

Worst case: \(O(n^2)\) comparisons and \(O(n^2)\) swaps. Average case: \(O(n^2)\) comparisons and \(O(n^2)\) swaps.

Best case: \(O(n)\) comparisons and \(O(1)\) swaps.

This is an in place algorithm.