In: Computer Science
Simple code please thats easy to follow.
C++
Write a program that can be used to compare Insertion Sort, Merge Sort and Quick Sort.
Program must:
Use your program to measure and record the time needed to sort random arrays of size 5000, 50000, and 500000. For each array size, obtain a printout of the time required for the sorts.
Please find the code below:
main.cpp
#include <iostream>
#include <stdlib.h>
#include <string>
#include <chrono>
#include <fstream>
#include <sstream>
using namespace std::chrono;
using namespace std;
//swap usign by selection sort
void swap(long *xp, long *yp)
{
long temp = *xp;
*xp = *yp;
*yp = temp;
}
// Get current date/time, format is YYYY-MM-DD.HH:mm:ss
const std::string currentDateTime() {
time_t now = time(0);
struct tm tstruct;
char buf[80];
tstruct = *localtime(&now);
// Visit
http://en.cppreference.com/w/cpp/chrono/c/strftime
// for more information about date/time format
strftime(buf, sizeof(buf), "%Y-%m-%d.%X",
&tstruct);
return buf;
}
/* Function to sort an array using insertion sort*/
void insertionSort(long arr[], int n)
{ cout<<"Insertion sort performance
"<<endl;
cout << "Start time : " << currentDateTime()
<<endl;
auto start = high_resolution_clock::now();
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i-1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
//check the time
cout << "End time : " << currentDateTime()
<<endl;
auto stop = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop -
start);
cout << "Elapse time : " << duration.count() << "
microseconds" << endl;
}
void selectionSort(long arr[], int n)
{
cout<<"Selection sort performance
"<<endl;
//clock to check time
cout << "Start time : " <<
currentDateTime() <<endl;
auto start = high_resolution_clock::now();
int i, j, min_idx;
// One by one move boundary of unsorted
subarray
for (i = 0; i < n-1; i++)
{
// Find the minimum element in
unsorted array
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] >
arr[min_idx])
min_idx = j;
// Swap the found minimum element
with the first element
swap(&arr[min_idx],
&arr[i]);
}
cout << "End time : " <<
currentDateTime() <<endl;
auto stop = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop
- start);
cout << "Elapse time : " <<
duration.count() << " microseconds" << endl;
}
int partition (long arr[], int low, int high)
{
float 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
if (arr[j] <= pivot)
{
i++; //
increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void quickSort(long 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 doQuickSort(long arr[], int high){
cout<<"Quick sort performance
"<<endl;
cout << "Start time : " <<
currentDateTime() <<endl;
auto start = high_resolution_clock::now();
quickSort(arr,0,high);
cout << "End time : " << currentDateTime()
<<endl;
auto stop = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop
- start);
cout << "Elapse time : " <<
duration.count() << " microseconds" << endl;
}
void copyArrayFunc(long source[],long dest[],int size){
for(int i=0;i<size;i++){
dest[i] = source[i];
}
}
void merge(long 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)
{
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++;
}
/* Copy the remaining elements of R[], if
there
are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(long arr[], int l, int r)
{
if (l < r)
{
int m = l+(r-l)/2;
mergeSort(arr, l, m);
for(int i=l;i<=m;i++){
}
mergeSort(arr, m+1, r);
for(int
i=m+1;i<=r;i++){
}
merge(arr, l, m, r);
}
}
void doMergeSort(long arr[], int r)
{
cout<<"\n\nMerge sort performance
"<<endl;
auto start = high_resolution_clock::now();
cout << "Start time : " <<
currentDateTime() <<endl;
mergeSort(arr,0,r);
cout << "End time : " << currentDateTime()
<<endl;
auto stop = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop
- start);
cout << "Elapse time : " <<
duration.count() << " microseconds" << endl;
}
int main()
{
//initialize array of 1000
long arraySize;
cout<<"Enter input size : ";
cin>>arraySize;
long array[arraySize];
long copyArray[arraySize];
//set all to zero
for(int i=0;i<arraySize;i++){
array[i] =rand()%100000;
}
copyArrayFunc(array,copyArray,arraySize);
insertionSort(copyArray,arraySize);
cout<<endl<<endl<<endl;
copyArrayFunc(array,copyArray,arraySize);
selectionSort(copyArray,arraySize);
cout<<endl<<endl<<endl;
copyArrayFunc(array,copyArray,arraySize);
doQuickSort(copyArray,arraySize-1);
copyArrayFunc(array,copyArray,arraySize);
doMergeSort(copyArray,arraySize-1);
return 0;
}
output: