Bubble Sort

The "Bubble Sort" algorithm uses the divide and conquer technique to recognize
• that in a list of two elements, the algorithm reduces to:
```
if (last_element > first_element) {swap positions}

```
to put this list in order, and

• by putting successive pairs of elements in order, the largest value in the list will be moved to the end.

```   (45   67)  13   22   36  =>
45  (67   13)  22   36  =>
45   13  (67   22)  36  =>
45   13   22  (67   36) =>
45   13   22   36   67
```

Thus using these two techniques repetitively and reducing the length of the list to be sorted by one element (the largest) each pass through, the whole list can be ordered. Thus to sort a list of n elements we firstly compare (n-1) overlapping pairs of elements, putting them in order, and then repeat that process for the shortened list of (n-1) elements. After sorting a list of (n-1) elements, then the next pass will involve (n-2) elements. Thus we can repeat this process successively until the list to be sorted is only of length 1, and we are guaranteed that the original list has been completely sorted.

This algorithm is shown on the next page.

The described algorithm will require (n-1) passes to completely sort the list of values. However this can be shortened by two techniques:

1. Keep track of whether any pair of elements is ever swapped - if not then the list is already sorted - quit!

2. Once a pair of elements have been exchanged, reverse the direction of the pair scanning until no exchange takes place. Reverse the direction again. This way when the algorithm looks at the last pair in the list and does not change their order, the list is sorted.

Last updated 2000/11/02