Wednesday, September 25, 2013

Insertion Sort Algorithm

Insertion Sort Algorithm start sorting from one end and traverse through the Insertion Sort Algorithm start sorting from one end and traverse through the array while ensuring the elements already read are in the correct order.

Take the first element of the array, consider it as sorted.

Then take the second element compare it with the previous if the first element is greater than the second then move the first element one cell backward and insert the second element in the first cell. Then we have a sorted array of two elements.

Then consider the third element and compare it with values of the previous cells move any element with value greater than the current element one cell forward and inset the current value in the correct place, this step results an array of three elements that are in the correct order.

Repeat these steps for all the elements in the array.

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

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.