Coding Notes

Ideas and thoughts from Seth Long

A Simple Bubble Sort

My blog is now located at http://www.WhoIsSethLong.com

Well, this is my first time writing online so I thought I’d start off with something simple and a bubble sort was the first thing that came to mind.  If you’re not familiar with what a bubble sort is, let me give you a quick rundown.

A bubble sort algorithm is a very simple way to sort a collection but also not a very efficient one.  The algorithm works by comparing 2 items in the collection and swapping them if they are not in the right position.  For example, we are going to sort the following array of numbers from smallest to largest.

6, 3, 8, 2, 5

The algorithm would start by comparing the first two numbers and moving the larger number to the right.

6, 3, 8, 2, 5   ->  3, 6, 8, 2, 5

The algorithm would then move over 1 place and compare the numbers there.

3, 6, 8, 2, 5

Since the larger number is already on the right, the algorithm doesn’t need to make any changes and again moves over to the right 1 position.

3, 6, 8, 2, 5

Now we have the larger number on the left so it will need to be swapped with the smaller number of the right.

3, 6, 8, 2, 5  ->  3, 6, 2, 8, 5

The larger number has been swapped to the right so the algorithm will now move over again and check the last two numbers.

3, 6, 2, 8, 5

Again, the larger number is on the left so it will need to be swapped.  This gives us:

3, 6, 2, 8, 5  ->  3, 6, 2, 5, 8

After the first pass through, we now have the largest number (8) in its proper position.  So now we will start at the beginning of the array again, work our way towards the end and swap numbers as needed.

3, 6, 2, 5, 8
3, 6, 2, 5, 8  ->  3, 2, 6, 5, 8
3, 2, 6, 5, 8  ->  3, 2, 5, 6, 8

Now, you can see that we don’t compare the last number this time.  That’s because we know the last number is already in it’s proper place.  Each run through the array we compare one less number on the right.  The algorithm gets its name because the largest number will bubble up to the last position after each pass.  Our third run through the array would look like this:

3, 2, 5, 6, 8  ->  2, 3, 5, 6, 8
2, 3, 5, 6, 8

Fourth run:

2, 3, 5, 6, 8

That’s definitely a lot of work just to sort 5 numbers.  There are other algorithms out there that are much more efficient then the bubble sort.

Coding the Bubble Sort Algorithm

Now that we hopefully understand how the bubble sort algorithm works, lets look at the code needed to implement it.  All we really need is 2 loops and an if statement to create a bubble sort algorithm.  The first and outer loop will start from the end of the array and work its way to the beginning.  The second and inner loop will start from the beginning of the array and work its way to the value of the outer loop.  Inside the inner loop is an if statement that compares the 2 numbers and swaps them if necessary.   Here is the code using C# syntax:

// the array to sort
int[] ary = new int[] { 6, 3, 8, 2, 5 };

// outer loop
for (int outer = ary.Length - 1; outer > 0; outer--)
{
    // inner loop
    for (int inner = 0; inner  ary[inner + 1])
    {
        // swap them
        int tmp = ary[inner];
        ary[inner] = ary[inner + 1];
        ary[inner + 1] = tmp;
    }
}

There are other variations of this algorithm but this is probably the most common way of coding it.

Efficiency

As I’ve mentioned before, the bubble sort algorithm is one of the worst ways to sort a collection.  To understand why, we need to look at the worst-case complexity of the algorithm.  Since the algorithm uses 2 loops to sort the array, there are a LOT of comparisons and swaps being made.  With an array of n items, the algorithm will make n – 1 comparisons on the first pass.  The next pass will require n – 2 comparisons, etc…  This gives us n(n – 1) / 2 or O(n2).

Well, that’s all for now.  I’ll be posting some more sorting algorithms soon so keep checking back!

– Seth Long

Advertisements

January 3, 2008 - Posted by | Algorithms

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: