Thursday, February 10, 2011

Bubble Sort

· is the oldest and simplest sort in use.

· Unfortunately, it's also the slowest.

· The bubble sort is generally considered to be the most inefficient sorting algorithm in common usage. Under best-case conditions (the list is already sorted), the bubble sort can approach a constant O(n) level of complexity. General-case is an abysmal O(n2).

· While the insertion, selection, and shell sorts also have O(n2) complexities, they are significantly more efficient than the bubble sort.

Pros: Simplicity and ease of implementation.

Cons: Horribly inefficient.

Steps in Bubble Sort:

1. Comparing each item in the list with the item next to it

2. Swap them if required (if not in correct order).

3. The algorithm repeats this process until it makes a pass all the way through the list without swapping any items (in other words, all items are in the correct order).

4. This causes larger values to "bubble" to the end of the list while smaller values "sink" towards the beginning of the list.

In summary, each complete pass through the list has the effect of pushing each value slightly closer to it’s sorted position. After a finite number of passes (at most N-1) the list must eventually become completely sorted.


Example:

Consider this example list, below. Let’s use bubble sort to order it in ascending order.

4 8 1 9 3


First we would compare 4 and 8. They are in the correct order. So we move to the next pair, 8 and 1. They are not in the correct order, so they are swapped. The list now looks like:

4 1 8 9 3


Now we compare 8 and 9. They are in the correct order, so we move on to compare 9 and 3, which are not correctly ordered, and so are swapped. The list now looks like like:

4 1 8 3 9


That concludes one single pass. We now start again from the beginning, for the second pass. 4 and 1 are out of order, so they are swapped, and the list becomes:

1 4 8 3 9


4 and 8 are already correct, so they are left as is. 8 and 3 however need to be swapped, so the list becomes:

1 4 3 8 9


Note that we don’t bother comparing 8 and 9 on the second pass, because we know they are already in the right order. Thus we now move straight to the next pass. By comparing 1 and 4, we find that they are correctly ordered.

But 4 and 3, the next pair, are not and so are swapped. This results in the list:

1 3 4 8 9


It can be seen quite obviously that this small example is now sorted. However, the bubble sort algorithm presented would still perform the next pass, obviously to no effect.


Empirical Analysis

Bubble Sort Efficiency

The graph clearly shows the n² nature of the bubble sort.


A fair number of algorithm purists (which means they've probably never written software for a living) claim that the bubble sort should never be used for any reason. Realistically, there isn't a noticeable performance difference between the various sorts for 100 items or less, and the simplicity of the bubble sort makes it attractive. The bubble sort shouldn't be used for repetitive sorts or sorts of more than a couple hundred items.

Source Code

Below is the basic bubble sort algorithm.


void bubbleSort(int numbers[], int array_size)

{

int i, j, temp;

for (i = (array_size - 1); i >= 0; i--)

{

for (j = 1; j <= i; j++)

{

if (numbers[j-1] > numbers[j])

{

temp = numbers[j-1];

numbers[j-1] =numbers[j];

numbers[j] = temp;

}
}
}
}

No comments:

Post a Comment