Sorting Algorithms in C The goal here is a comparative exper

Sorting Algorithms in *(C++)*: The goal here is a comparative experimental study, in terms of running time, of the following 4 sorting algorithms. • Insertion sort. • Mergesort. • Quicksort. 1. Implement the 4 algorithms above within the same program. The input and output are described as follows. Input: 2 parameters N (number of random naturals to sort) and K (used by Quick-insertion). Output: Display the list of N randomly generated naturals. For each algorithm display the list of sorted numbers + corresponding running time. 2. Find the pair of values (N, K) where : (a) Quick-insertion outperforms all the other algorithms. (b) Insertion sort outperforms all the other algorithms. (c) Quicksort outperforms all the other algorithms.

Solution

Hi,

Your program is as follows which represents the all the algorithms and running time of that particular algorithms.

Program :

#include<iostream>
#include<stdlib.h>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;

template<class T>
void isort(T a[],int n)
{
     int i;
     for(i=1;i<n;i++)
     {
             T t=a[i];
             int j;
             for(j=i-1;j>=0&&t<a[j];j--)
             {
                                           a[j+1]=a[j];
             }
             a[j+1]=t;
     }
}

void m_sort(T nos[],T t[],int l,int r);

template<class T>
void mergesort(T nos[],T t[],int asize)
{
     m_sort<T>(nos,t,0,asize-1);
}

template<class T>
void m_sort(T nos[],T t[],int l,int r)
{
     int mid;
     if(r>l)
     {
                   mid=(r+l)/2;
                   m_sort(nos,t,l,mid);
                   m_sort(nos,t,mid+1,r);
                   merge(nos,t,l,mid+1,r);
     }
}

template<class T>
void merge(T nos[],T t[],int l,int mid,int r)
{
     int i,l_end,num_elements,t_pos;
         l_end=mid-1;
         t_pos=l;
         num_elements=r-l+1;
         while((l<=l_end)&&(mid<=r))
         {
                                              if(nos[l]<=nos[mid])//(kept -nos instead )
                                              {
                                                                              t[t_pos]=nos[l];
                                                                              t_pos++;
                                                                              l++;
                                              }
                                              else
                                              {
                                                                              t[t_pos]=nos[mid];
                                                                              t_pos++;
                                                                              mid++;
                                              }
         }
         while(l<=l_end)
         {
                               t[t_pos]=nos[l];
                               l++;
                               t_pos++;
         }
         while(mid<=r)
         {
                          t[t_pos]=nos[mid];
                          mid++;
                          t_pos++;
         }
         for(i=0;i<=num_elements;i++)
         {
                                     nos[r]=t[r];
                                     r--;
         }
}

int part(int low,int high,int *a)
{
     int i,h=high,l=low,p,t; //p==pivot
     p=a[low];
     while(low<high)
     {
                    while(a[l]<p)
                    {
                                   l++;
                    }
                    while(a[h]>p)
                    {
                                   h--;
                    }
                    if(l<h)
                    {
                                t=a[l];
                                a[l]=a[h];
                                a[h]=t;
                    }
                    else
                    {
                        t=p;
                        p=a[l];
                        a[l]=t;
                        break;
                    }
     }
     return h;
}

void quick(int l,int h,int *a)
{
int index,i;
if(l<h)
{
          index=part(l,h,a);
          quick(l,index-1,a);
          quick(index+1,h,a);
}
}

void main()
{
    int a[100],,b[100],i,n,K,h,l;
    double t1,t2;
    cout<<\"Enter number of elements : \";
    cin>>n;
    cout<<\"Enter elements (Use Spacebar as Separator)\ \";
    for(i=0;i<n;i++)
    {
                    cin>>a[i];
    }
    cout<<\"Enter to choose sorting method : \";
    cout<<\"1.Insertion Sort\ \";
    cout<<\"2.Merge Sort\ \";
    cout<<\"3.Quick Sort\ \";
    cin>>K;
    if(K==1){
   t1 = clock();   
       isort(a,n);
   t2 = clock();
        cout<<\"After sorting the elements are\ \";
        for(i=0;i<n;i++)
        {
                    cout<<a[i]<<\"\ \";
        }
        cout<<\"Running time :\" << (t2-t1)/CLK_TCK <<\" sec\ \";
     
    }  
    if(K==2){
   t1 = clock();   
       mergesort(a,b,n);
   t2 = clock();
        cout<<\"After sorting the elements are\ \";
        for(i=0;i<n;i++)
        {
                    cout<<a[i]<<\"\ \";
        }
        cout<<\"Running time :\" << (t2-t1)/CLK_TCK <<\" sec\ \";
    }
    if(K==3){
   h=n-1;
   l=0;
   t1 = clock();   
       quick(l,h,a);
   t2 = clock();
        cout<<\"After sorting the elements are\ \";
        for(i=0;i<n;i++)
        {
                    cout<<a[i]<<\"\ \";
        }
        cout<<\"Running time :\" << (t2-t1)/CLK_TCK <<\" sec\ \";
    }
    system(\"pause\");
}