Category Archives: Algorithms

Insertion Sort

Input: sequence of n nos a1,a2,a3…
Output: permutation of those numbers such that a1′<=a2′<=a3′..
It’s an effective algo for sorting small no of elements.

Find the correct position and the insert it
To find the correct position we compare with the nos already present
Check with each element. The whole array would be sorted after the process. i.e, check with each element and insert it before or after.

So It takes in i/p an array of n elements A[1-n] in sorted order
During insertion, the nos are rearranged within the array and sorted.


void insertion_sort(int unsorted[],int number_of_elements)
{
 int i,j,key;
 for(j=2;j&lt;=number_of_elements;j++)
 {
key=unsorted[j];
i=j-1;
while(i>0 && unsorted[i]>key)
{
unsorted[i+1]=unsorted[i];
i=i-1;
}
unsorted[i+1]=key;
}
}

Just an example
5 | 2 | 4 | 6 | 1 | 3 |
Key = 2 unsorted[j]
unsorted[i]>key, 5>2
unsorted[i+1]=unsorted[i], unsorted[2]=unsorted[1]=5
i=i-1=0, unsorted[i+1]=key=2

2 | 5 | 4 | 6 | 1 | 3 |
2 | 4 | 5 | 6 | 1 | 3 |
1 | 2 | 4 | 5 | 6 | 3 |    in loop. Checks with all previous elements
1 | 2 | 3 | 4 | 5 | 6 |

Complete implementation can be found at https://github.com/sowmyaravidas/Sorting-Algorithms

Selection Sort

Here we find the smallest element in the list and swap it with the first element. Then the second smallest, swapping with second element and so on. This is done till (n-1) times. And number of swaps required is n-1.

5 4 3 2 1
1 4 3 2 5
1 2 3 4 5
1 2 3 4 5
Well, the time complexity is O(n*n) which is same as https://sowmyaravidas.wordpress.com/2012/10/06/bubble-sort/

But selection is better since number of swaps required is less.

void selection_sort(int unsorted[],int number_of_elements)
{
int minimum;
int temp;
int minimum_position;
for(int i=0;i<number_of_elements;i++)
   {
    minimum=unsorted[i];
    for(int j=i+1;j<number_of_elements;j++)
    {
     if(minimum>unsorted[j])
     {
      minimum=unsorted[j];
      minimum_position=j;

      temp=unsorted[i];
      unsorted[i]=unsorted[minimum_position] ;
      unsorted[minimum_position]=temp;
      }
    }
  }
}

Complete implementation of the code can be found at https://github.com/sowmyaravidas/Sorting-Algorithms

Bubble Sort

This is a brute force method of sorting.  Compare the successive elements from position 1 to last. This is one
iteration. Do till (n-1) times.

5 4 3 2 1
4 5 3 2 1
4 3 5 2 1
4 3 2 5 1
4 3 2 1 5
This is iteration1. So at the end, maximum element moves to the end.

The time complexity of this algorithm is O(n*n).


 void bubble_sort(int unsorted[],int n)
 {
     int temp;
    for(int i=0;i<number_of_elements-1;i++)
    {
       for(int j=0;j<number_of_elements-i-1;j++)
       {
            if(unsorted[j]>unsorted[j+1])
             {
                 temp=unsorted[j];
                 unsorted[j]=unsorted[j+1];
                 unsorted[j+1]=temp;
             }
        }
     }

Complete implementation can be found at https://github.com/sowmyaravidas/Sorting-Algorithms