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

Algorithm of Quicksort

Written by Kousik : 
 QUICKSORT(S)

 {

1.       If ||S||<=1 return;

else {

       2.                Select a first element e as pivot from s.

       3.                 Compare elements of s with e to partition S into subsets S₁, S₂, S₃  such that

                               Elements of S₁ are less than e.

                                Elements of S₂ are equal to e.

                                Elements of S₃ are greater than e.

      4. return (QUICKSORT(S₁), followed by S₂, QUICKSORT(S₃)) ;

}

Implementation of step 2 [Partitioning]

1)      Select the very first element of S as pivot.(Simplest implementation)

2)      Select pivot from S at random.(Randomized implementation)

Analysis of Time complexity of this algorithm:

Let T(n) be the time complexity of this algorithm.

i)                    Worst Case

T(n) = T(0) + T(n-1) + n -1

        = 1+ T(n-1) + n -1

        = T(n-1)+n

        = n(n+1)/2 = O(n²)

This is a polynomial in time complexity. So this is a nice algorithm for solving a sorting problem. But we use this algorithm in a better way such that the time complexity of this algorithm reduced to O(nlogn).

ii)                   Best Case:

<- n/2 elements

->n/2 elements

Time complexity will be

                        T(n)=2T(n/2)+n

                        T(n)=O(nlogn)

iii)                 Average case:

                      [Assumption: all elements of S are equal probable to be the pivot in QUICKSORT(S)]

Let ith smallest element appear as pivot then

T(n)=n -1+T(i-1)+T(n-i)

        =cn+T(i-1)+T(n-i)

Total time require by randomized quick sort algorithm is T(n).

T(n)=(1/n)

Assume T(0)=T(1)=b

Then T(n)=(1/n)

           T(n)=(1/n)

                  = cn+(1/n)

                   = cn+(2/n)

                   = O(nlogn) [ for proof follow this book: Design and analysis of algorithm (aho: hofcroft: ullman)]

Now it is time for writing the average or randomized algorithm for quick sort.

Same procedure will be used in here except the method of pivot element.

QUICKSORT(S)

 {

1.       If ||S||<=1 return;

else {

       2.                select an element e as pivot from s in a random manner.

       3.                 compare elements of s with e to partition S into subsets S₁, S₂, S₃  such that

                               Elements of S₁ are less than e.

                                Elements of S₂ are equal to e.

                                Elements of S₃ are greater than e.

      4. return (QUICKSORT(S₁), followed by S₂, QUICKSORT(S₃)) ;

}

See carefully at the line 2.

Before the pivot was the very first element but now it would be any element of s.

This is the big advantage of randomized quick sort algorithm.

Now we have to write the C code for randomized quick sort algorithm.

/* A program for randomized quick sort*/

#include<stdio.h>

#include<stdlib.h>

int *a,n;

void swap(int *a1,int *a2)/* function for swapping two element*/

{

      int k;

       k=*a1;

      *a1=*a2;

      *a2=k;

}

int partition(int i,int j)/* function for partition the array into three sub arrays*/

{

             int x,p,v;

                x=a[j];

                p=i-1;

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

                {

                 if(a[v]<=x)

                 {

                  p++;

                  swap(a+p,a+v);

                 }

                }

              swap(&a[p+1],&a[j]);

                return(p+1);

}

int rand_partition(int i,int j)/* function to finding the random number*/

{

     int q;

     q=rand()%(j-i)+i;

     swap(a+q,a+j);

     return partition(i,j);  

}

void quicksort(int i,int j)/* function for main alogorithm QUICKSORT(S)*/

{

     

    int b;

    if(i<j)

    {

       b=rand_partition(i,j);

       quicksort(i,b-1);

       quicksort(b+1,j);

    }

    else

    return;

}

void main()

{

    int i;

    printf("\n Enter the number of elements in the array: ");

    scanf("%d",&n);

    a=(int*)malloc(n*sizeof(int));

    printf("\n Enter the elements in the array: ");

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

    scanf("%d",a+i);

    printf("\n The array before sorting is: ");

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

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

    quicksort(0,n-1);         

    printf("\n");

    printf("\n The array after sorting is:");

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

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

    printf("\n");

    return;

}
Continued...  

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