Bubble Sort

Bubble Sort examines every pair of elements, and swaps them if they are out of order.
It really has only two redeeming features;

For some reason, bubble sort is frequently used as an example of how computers do sorting.
I think this is because the code is small, and teachers confuse "small" with "easy to understand".
In the days of BASIC, before procedural programming was all the rage, it might even have been true.
These days, I strongly recommending mentioning selection sorting first, then teaching insertion sort, before going on to divide and conquer.

Bubble sort is called bubble sort because at each step it moves a single element (at most) one place in the list.
If you iterate starting from the end of the list, it moves the smallest value to the beginning of the list and the larger values one to the right.
It can be thought of as selection sort, with the added disadvantage that as we search for the lowest value, we swap the current value with every element in the list.

Classic Bubble Sort is O(N2).

5 1 3 6 4 2 3 1 2 5 6 4 Steps 1-6 Steps 7-11 Steps 12-15 Steps 16-18 5 3 1 6 4 2 Steps 19-20 Step 21 3 1 2 5 6 4 3 1 2 5 6 4 3 1 2 5 6 4 3 1 2 5 6 4 4 2 2 1 1 2 2 4 2 4 2 Done

Bubble sort can in theory be done in parallel, in which case it's O(N)
You swap even indexed with odd indexed, then odd indexed with even.

Pass 1 Pass 2 Pass 3 Pass 4 5 3 1 6 4 2 Bubble Sort In Parallel Pass 5 Pass 6 3 1 2 5 6 4 5 3 1 6 4 2 5 3 1 6 4 2 5 3 1 6 4 2 5 3 1 6 4 2 5 3 1 6 4 2 Done

In practice, no one cares enough about sorting to build this kind of special purpose hardware.

An aside; When I was at college, the professor of my CIS 101 class tried to have the students do a human bubble sort in parallel.
However, he didn't consider that the auditorium wasn't full, that students at the ends of the rows might not know who to swap with, and that not all students would dutifully follow his instructions like a computer, or that he might have made a mistake in the instructions.
The ensuing chaos taught me two very important lessons;

^ UP ^    < Back <    > Next >