**Bubble
Sort**

(Up to Basic
Computer Science : Lists and Arrays
: Sorting Algorithms)

**Bubble Sort** is by far the **simplest and shortest** of
all the sorting algorithms. Here is the code for it:

( About
Example C++ code )
**void** bubblesort(** int** array[], **int** n )
{
**for** ( **int** i = 0; i < n-1; ++i )
**for** (** int** j = 1; j < n-i; ++j )
**if** ( array[j-1] > array[j] )
swap( array[j-1], array[j] );
}

You can see why we call this a short algorithm. Even though it's
short, I will explain it anyway.

Basically, this algorithm goes through the entire array and compares
every adjacent pair of elements in the array starting from the first
and working towards the last. This cycle is repeated over and over
until the entire array is sorted.

Notice that at the end of each cycle, the last element, and then
the next to last element, and so on is in place. Thus, the cycle
is shortened by one element each time so that we don't have to bother
with the last elements which are already in place.

Let us walk through this algorithm on an example: 3
2 5 4 1. Note that n = 5.

**First Iteration ( i = 0 ):** We are considering the array 3 2 5 4 1.

**( j = 1 ):** 3 > 2, so swap()
and the array is now 2 3 5 4 1.

**( j = 2 ):** 3 < 5, so nothing
happens and the array is still 2 3 5 4 1.

**( j = 3 ):** 5 > 4, so swap()
and the array is now 2 3 4 5 1.

**( j = 4 ):** 5 > 1, so swap()
and the array is now 2 3 4 1 5.

j is no longer strictly less than n
- i, so we are finished with the **First Iteration**.

**Second Iteration ( i = 1 ):** We are now considering the array 2 3 4 1. (**Not** the last one, remember? n - i = 4, so we only consider the first
4 elements.)

**( j = 1 ):** 2 < 3, so nothing
happens and the array is still 2 3 4 1.

**( j = 2 ):** 3 < 4, so nothing
happens and the array is still 2 3 4 1.

**( j = 3 ):** 4 > 1, so swap()
and the array is now 2 3 1 4.

j is no longer strictly less than n
- i, so we are finished with the Second Iteration.

**Third Iteration ( i = 2 ):** We are now considering the array 2 3 1.

**( j = 1 ):** 2 < 3, so nothing
happens and the array is still 2 3 1.

**( j = 2 ):** 3 > 1, so swap()
and the array is now 2 1 3.

j is no longer strictly less than n
- i, so we are finished with the Third Iteration.

**Fourth Iteration ( i = 3 ):** We are now considering the array 2 1.

**( j = 1 ):** 2 > 1, so swap()
and the array is now 1 2.

j is no longer strictly less than n
- i, so we are finished with the Fourth Iteration.

Now i is no longer strictly less than n-1, so we are finished sorting.

Now that you have seen the entire sorting process written out,
the algorithm will make more **sense** to you.

One of the problems with Bubble Sort is that even when the array
is fully sorted, the sort continues. This problem, however, is easily
remedied: just insert a **boolean flag** that keeps track of
whether or not the sort called swap()
on anything in the last iteration. If it did not, then the sort
has finished early.

Still, improving the efficiency of the Bubble Sort algorithm is
really quite a useless effort. **If you want more efficiency, use
another algorithm**. The reason for using Bubble Sort is because
it is easy to type, so making Bubble Sort more complex is not really
all that appealing.

If you would like a usable version of the Bubble Sort algorithm,
there is one below that uses templates. The only efficiency improvement
to Bubble Sort is the early exit flag, since that does not add much
length to the code.

**Download from Source
Code Repository:** sorts/bubble.h