The purpose of the below program is to perform empirical analysis of the followi

Question

The purpose of the below program is to perform empirical analysis of the following sorting algorithms on integer arrays.

(a) Quicksort;

(b) Mergesort.

(c) Two versions of a bubble sort: with and without counting the number of swaps on each pass through an array;

Write a C++ program for obtaining the running or working times of each algorithm for a particular array(Use gethrtime function).Call this function before and after a call to the function implementing a sorting algorithm listed above.

Requirements:

a) Run your functions for the following types of arrays containing 1000, 10000 and 100000 integers: random numbers, sorted list, almost sorted list (say, each 10th number is out of order).

b) The size of integers is supposed to be from 1 to 10000.

Explanation / Answer

a:

#include<iostream>
#include<conio.h>
using namespace std;

//Function for partitioning array
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);
}
}

int main()
{
      int a[100],n,l,h,i;
      cout<<"Enter number of elements:";
      cin>>n;
      cout<<"Enter the elements (Use Space As A Separator):";
      for(i=0;i<n;i++)
      cin>>a[i];
      cout<<" Initial Array: ";
      for(i=0;i<n;i++)
      {
                      cout<<a[i]<<" ";
      }   
      h=n-1;
      l=0;
      quick(l,h,a);
      cout<<" After Sorting: ";
      for(i=0;i<n;i++)
      {
                cout<<a[i]<<" ";
      }
      getch();
      return 0;
}

b:

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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