Sorting Algorithms in *(C++)*: The goal here is a comparative experimental study

Question

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.

Explanation / Answer

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");
}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.