Algorithm of Insertion Sort

Written by Kousik : 

This is another efficient way of solving a problem related with sorting. This algorithm works as the way people play cards. We present our procedure for insertion sort by the name INSERTION. This function takes an array of n element as input which is to be sorted. This algorithm sorts given n elements by inserting them into their right position.

Procedure INSERTION

{

  For i=1 to n-1 do

  Insert(i);

 

}

Insert(i)/* assumes a[0], a[1],…,a[i-1] are sorted*/

{                  /* Insert a[i] in appropriate position so that a[0],a[1],…a[i-1],a[i] become sorted*/

}

Time complexity of this algorithm:

Look carefully in the algorithm you will see that the algorithm works for each element in the array by keeping a particular element into its right position. So the time complexity will be

                                T(n) =

                                     =n(n+1)/2

                                        <=n²/2=O(n²)

So it is efficient algorithm because it takes the polynomial time complexity for executing.

Now we have to write the C code for this algorithm

/* A c program for insertion sort*/

#include<stdio.h>

#include<stdlib.h>

int *a,n;

void insert();

int main()

{

  int i;

  printf("Enter the total number of elements: ");

  scanf("%d",&n);

  a=(int *)calloc(n,sizeof(int));

  printf("Enter the values: ");

  for(i=0;i<n;i++)

  scanf("%d",&a[i]);

  insert();

  printf("The sorted array: ");

  for(i=0;i<n;i++)

  printf("%d ",a[i]);

  return 0; 

}

void insert(void)

{

    int i,j,temp;

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

                {

                  temp=a[i];

                  j=i-1;

                  while((temp<a[j])&&(j>=0))

                  {

                  a[j+1]=a[j];

                  j=j-1;

                  }

                  a[j+1]=temp;

                }

}

Continue

Sorting

Written by Kousik : 

“Sorting”, this word must come when you are reading C programming language as well as algorithm. This is important part of C programming and very interested problem. Many algorithms for sorting are there. In this section we discuss about several sorting algorithms and their time and space complexity.

Definition:

Input: A sequence of n numbers from linearly ordered set or totally ordered set.

Output: A permutation of the given input sequence such that a[i] <=a[i+1] , where I =1,2,3…,n

Sorting algorithms:

There are many algorithms for sorting. Every algorithm took some time for performing. Different algorithms for same problem would take different complexity.

Problem: Sorting

Name of algorithms	Time complexity	Space Complexity
Insertion sort	O( )	O(n)
Bubble sort	O( )	O(n)
Quick sort	O(nlogn) (In Expected case)	O(n)
Heap sort	O(nlogn)	O(n)
Radix sort or bucket sort	O(n)	O(n)

Now we will analysis about the algorithms shown in above table:

Quick Sort:

This is a way of solving a problem related with sorting. This is a divide-conquer method for sorting. It works by following rule.

1)      Partition the array into two parts.

2)      Sort the two sub array.

3)      Combine the solutions to get the solution for main problem.

Mainly the performance of this method depends upon the position where the partition is to be done. Partition can be done by three following ways.

1)      At first or last position.(Worst case)

2)      At middle position.(Best case)

3)      Randomly choose an element for partition(Randomized quick sort)

We will call the partitioning element by name ‘PIVOT’.

After selecting pivot element we scan the whole array. If we find an element greater than or equal to the pivot element then we keep it at right side of pivot element and otherwise keep it in left side.

By doing this we can claim that the pivot element gets it right position into the array. Then we recursively call the function to right and left side. So, at the end we will get the sorted array.

First we select the middle element as pivot element.

Now it is the time for writing the algorithm.

Method: We use a function named QUICKSORT(S) which works recursively.

Input: Sequence S of n elements a_1, a₂ ...a_n

Output: The elements of S in sorted order.
Continued...  

Continue