1.0040 Describe how a bubble sort (one-way, two-way, with and without sorted flags) works. When is a bubble sort appropriate?

A bubble sort works by ‘bubbling’ the larger elements to the top of the list or ‘bubbling’ the smaller elements to the bottom of the list (depending on the direction of the sort, and whether or not the list is to be sorted in ascending order or descending order).

We know that a list is sorted if we can make one pass through it without making any swaps. A ‘flag’ is used to check that condition. If we do not use a ‘flag’, we need to make the maximum number of passes (n-1, where n is the number of elements on the list) and (n² – n)/2 comparisons. If we do use a ‘flag’, we need to make 1 (one) additional pass after the list has been sorted.