Showing posts with label Sorting. Show all posts
Showing posts with label Sorting. Show all posts

Wednesday, April 17, 2013

Bubble Sort algorithm

The Bubble Sort algorithm is named as such after the way in which values bubble to the top.

It is a suitable sorting algorithm for small unsorted lists and arrays.

You may like to watch the video at the end of this post before reading on (skip to about 50 seconds in).

Let's take the example of a small array of 5 elements:

int numList[] = {100,40,2,1,89};

In it's sorted form, the list of numbers would look like this:

1,2,40,89,100

So how do we get there?

Using a for-loop, we will bubble sort the values by checking if the current value is greater than the next value in the array:

for (int x = 0; x < numList.length - 1; x++) {

if (numList[x] > numList[x+1] )

If true, we need to swap the numbers in the array, but to do so, we will need to store the current value in a temporary variable, so that the next value can be placed into the current value's place in the array - like so:

int temp = numList[x];
numList[x] = numList[x+1];
numList[x+1] = temp;




If false, we do nothing and allow the loop to continue.

Note that the loop is primed so that the loop counter (x) is never greater than the array's length minus one - which in this example would mean that x is never greater than 3. This is because the final swap possible is between indexes 3 & 4 and we don't want to generate an ArrayIndexOutOfBoundsException when we execute the expression numList[x+1].

If the length of the list we need to sort is 5, it will take 4 loops to sort the list, once.

First pass:
100,40,2,1,89 becomes 40,2,1,89,100

We can see that 100 has bubbled to the end of the list, however, the list is still not sorted. If the length of the list is 5, it will take 16 loops (maximum) to ensure that each position is sorted.

We will need to use an outer loop and and inner loop (nested loops) to ensure that all elements are sorted.


And here is the output of each outer loop:


Note that in this example, it actually only took 3 outer loops (12 loops total) to sort the array. If we used the following array:

5,4,3,2,1

... it would take 16 repetitions to sort the array completely - this is because the largest number in the array (5) is in the first position and therefore has the entire length of the array to be sorted through.

Here's the output of bubble sorting that list:



The video is quite cool :)