Tuesday, September 24, 2013

Bubble Sort Algorithm

Bubble Sort Algorithm is one of the simplest sorting algorithms. Basic idea is to move either the largest or the smallest value to either to backward or to forward until the given data set is sorted.

If you want the array to be sorted in ascending order, compare each element in the in the array while traversing and bring the largest to the last cell of the array. Then we have an array with unsorted elements and the largest value at the last cell.

Then again traverse the array and bring the next largest value you find to the cell before the last, which results an array with unsorted elements with two cells at the back having largest values and are properly ordered in ascending order.

Repeat these steps until a sorted array is resulted.

At each repeat reduce the traversing length by one, as the rest of the array is already sorted in the previous traversal.

Bubble Sort Algorithm, C++ implementation
void BubbleSord(int* A, int length)
    int temp = 0;
    for (int i = 1; i < length; i++)
        for (int j = 1; j <= length - i; j++)
            if (A[j - 1] > A[j])
                temp = A[j];
                A[j] = A[j - 1];
                A[j - 1] = temp;

Below is a good illustration of the Bubble Sort Algorithm. Algorithm explained in this video is a little bit different. But the concept is the same.

No comments:

Post a Comment