Hello guys. I need some help doing the code for this confusing C++ assignment: A
ID: 3721085 • Letter: H
Question
Hello guys. I need some help doing the code for this confusing C++ assignment:
Assignment Sorting
Benchmark each of the sorting methods listed below.
Insertion Sort
Bubble Sort
Selection Sort
Heap Sort.
Quick Sort.
Merge Sort.
Benchmark each of the above sorting methods for data sizes of 10000, 20000, 30000, 40000 and 50000. Display the results in a table as shown below. The table should have rows and columns. However, the rows and columns need not be separated by lines. Add two more columns for Selection and Insertion Sorts
Data Size
Heap Sort Time In Seconds
Merge Sort Time In Seconds
Quick Sort Time In Seconds
Bubble Sort
100000
200000
300000
400000
500000
Notes:
Do not use a local array for keeping data values. Use a global array for this purpose. You can use dynamically allocated arrays if you wish.
Generate the data using a random generator and store it in a global array for use in sorting. If you use a local array of large size, you will run out of stack space.
Calculate the time taken by a sort routine in seconds as below:
#include
clock_t start, finish;
start =clock( ); //time in milliseconds
sort( );
finish=clock( ); //time in milliseconds
//the constant CLOCKS_PER_SEC below is equal to 1000
double duration = (double) ( (finish-start)/CLOCKS_PER_SEC ); //time in secs.
cout <
Data Size
Heap Sort Time In Seconds
Merge Sort Time In Seconds
Quick Sort Time In Seconds
Bubble Sort
100000
200000
300000
400000
500000
Explanation / Answer
#include<iostream>
#include<cstdlib>
#include<sys/time.h>
using namespace std;
class Sort
{
int nswap[5],compr[5];
public:
Sort()
{
int i=0;
for(i=0;i<5;i++)
{
nswap[i]=compr[i]=0;
}
}
void swap(int arr[],int i, int j)
{
double temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
void displayarray(double arr[],int n)
{
int i;
cout<<(" Array after sorting: ");
for(i=0;i<n;i++)
cout<<arr[i]<<" ";
}
void selectionSort(int arr[],int n)
{
// One by one move boundary of unsorted subarray
for (int i = 0; i < n-1; i++)
{
compr[0]++; // Find the minimum element in unsorted array
int min_idx = i;
for (int j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
if(min_idx != i)
{
swap(arr,min_idx , i);
nswap[0]++; }
}
}
void bubbleSort(int arr[],int n)
{
// One by one move boundary of unsorted subarray
for (int i = 1; i < n; i++)
{ compr[1]++;
for (int j = 0; j < n-i; j++)
if (arr[j] > arr[j+1])
{
swap(arr,j, j+1);
nswap[1]++;
}
}
}
void insertinSort(int arr[],int n)
{
for (int i=1; i<n; ++i)
{
int key = arr[i];
int j = i-1;
compr[2]++;
while (j>=0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
nswap[2]++;
}
arr[j+1] = key;
nswap[2]++;
}
}
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element
for (int j = low; j <= high- 1; j++)
{
// If current element is smaller than or
// equal to pivot
compr[3]++;
if (arr[j] <= pivot)
{
i++; // increment index of smaller element
swap(arr,i, j);
nswap[3]++;
}
}
swap(arr,i + 1, high);
nswap[3]++;
return (i + 1);
}
/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int L[n1], R[n2];
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2)
{
compr[4]++;
nswap[4]++;
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy the remaining elements of L[], if there
are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
nswap[4]++;
}
/* Copy the remaining elements of R[], if there
are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
nswap[4]++;
}
}
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l+(r-l)/2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
/* UTILITY FUNCTIONS */
/* Function to print an array */
void printArray()
{
int i;
cout<<" Swap";
for (i=0; i < 5; i++)
cout<<" "<<nswap[i];
cout<<" Compr";
for (i=0; i < 5; i++)
cout<<" "<<compr[i];
}
void reset()
{
int i=0;
for(i=0;i<5;i++)
{
nswap[i]=compr[i]=0;
}
}
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i)
{
swap(arr,i,largest);
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
// main function to do heap sort
void heapSort(int arr[], int n)
{
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (int i=n-1; i>=0; i--)
{
// Move current root to end
swap(arr,0,i);
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
};
int main()
{
Sort S;
int *a,*b,i,j,k=1,n;
typedef struct timeval time;
time stop,start;
while(k<6)
{
cout<<"eneter the value of n: ";
cin>>n;
a=new int[n];
b=new int[n];
for(i=0;i<n;i++)
{
a[i]=rand();
b[i]=a[i];
}
cout<<"Times in Micoro Second: ";
cout<<"Datasize "<<" Selection "<<" Bubble "<<" Insertion ";
cout<<" Quick "<<" Merge "<<" Heap "<<" ";
cout<<n<<" ";
gettimeofday(&start,NULL);
S.selectionSort(a,n);
gettimeofday(&start,NULL);
if(stop.tv_sec>start.tv_sec)
cout<<" "<<stop.tv_sec-start.tv_sec;
else
cout<<" "<<stop.tv_usec-start.tv_usec;
for(i=0;i<n;i++)
a[i]=b[i];
gettimeofday(&start,NULL);
S.bubbleSort(a,n);
gettimeofday(&start,NULL);
if(stop.tv_sec>start.tv_sec)
cout<<" "<<stop.tv_sec-start.tv_sec;
else
cout<<" "<<stop.tv_usec-start.tv_usec;
for(i=0;i<n;i++)
a[i]=b[i];
gettimeofday(&start,NULL);
S.insertinSort(a,n);
gettimeofday(&start,NULL);
if(stop.tv_sec>start.tv_sec)
cout<<" "<<stop.tv_sec-start.tv_sec;
else
cout<<" "<<stop.tv_usec-start.tv_usec;
for(i=0;i<n;i++)
a[i]=b[i];
gettimeofday(&start,NULL);
S.quickSort(a,0,n-1);
gettimeofday(&start,NULL);
if(stop.tv_sec>start.tv_sec)
cout<<" "<<stop.tv_sec-start.tv_sec;
else
cout<<" "<<stop.tv_usec-start.tv_usec;
for(i=0;i<n;i++)
a[i]=b[i];
gettimeofday(&start,NULL);
S.mergeSort(a,0,n-1);
gettimeofday(&start,NULL);
if(stop.tv_sec>start.tv_sec)
cout<<" "<<stop.tv_sec-start.tv_sec;
else
cout<<" "<<stop.tv_usec-start.tv_usec;
for(i=0;i<n;i++)
a[i]=b[i];
gettimeofday(&start,NULL);
S.heapSort(a,n-1);
gettimeofday(&start,NULL);
if(stop.tv_sec>start.tv_sec)
cout<<" "<<stop.tv_sec-start.tv_sec;
else
cout<<" "<<stop.tv_usec-start.tv_usec;
cout<<endl;
delete(a);
delete (b);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.