Question

In: Computer Science

Simple code please thats easy to follow. C++ Write a program that can be used to...

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:

  • Read an array size from the user, dynamically an array of that size, and fill the array with random numbers
  • Sort the array with the Insertion Sort, MergeSort and QuickSort algorithms studied in class, doing a time-stamp on each sort.

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.

Solutions

Expert Solution

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:


Related Solutions

Please make it simply and easy for a beginner to follow.. -Write in C++ -Use Char...
Please make it simply and easy for a beginner to follow.. -Write in C++ -Use Char library functions -Must show that is runs Write a function that accepts a string representing password and determines whether the string is a valid password. A valid password as the following properties: 1. At least 8 characters long 2. Has at least one upper case letter 3. Has at least one lower case letter 4. Has at least one digit 5. Has at least...
Please make it simply and easy for a beginner to follow -Write in C++ -Use Char...
Please make it simply and easy for a beginner to follow -Write in C++ -Use Char library functions Write a function that accepts a string representing password and determines whether the string is a valid password. A valid password as the following properties: 1. At least 8 characters long 2. Has at least one upper case letter 3. Has at least one lower case letter 4. Has at least one digit 5. Has at least on special characte
Write a code for simple racing game (using dots) on c program.
Write a code for simple racing game (using dots) on c program.
Code in C# please. Write a program that will use the greedy algorithm. This program will...
Code in C# please. Write a program that will use the greedy algorithm. This program will ask a user to enter the cost of an item. This program will ask the user to enter the amount the user is paying. This program will return the change after subtracting the item cost by the amount paid. Using the greedy algorithm, the code should check for the type of bill. Example: Cost of item is $15.50 User pays a $20 bill $20...
*Please write code in C++* Write a program to verify the validity of the user entered...
*Please write code in C++* Write a program to verify the validity of the user entered email address.   if email is valid : output the stating that given email is valid. ex: "The email [email protected] is valid" else : output the statement that the email is invalid and list all the violations ex:  "The email sarahwinchester.com is invalid" * @ symbol * Missing Domain name The program should keep validating emails until user enter 'q' Upload your source code. ex: main.cpp
please write simple python code Write a program to replicate the behavior of UNIX utility “tail”....
please write simple python code Write a program to replicate the behavior of UNIX utility “tail”. It takes one or more files and displays requested number of lines from the ending. If number is not specified, then it print 10 lines by default.
C++ program, I'm a beginner so please make sure keep it simple Write a program to...
C++ program, I'm a beginner so please make sure keep it simple Write a program to read the input file, shown below and write out the output file shown below. Use only string objects and string functions to process the data. Do not use c-string functions or stringstream (or istringstream or ostringstream) class objects for your solution. Input File.txt: Cincinnati 27, Buffalo 24 Detroit 31, Cleveland 17 Kansas City 24, Oakland 7 Carolina 35, Minnesota 10 Pittsburgh 19, NY Jets...
Code in C++ please You are going to write a program for Computer test which will...
Code in C++ please You are going to write a program for Computer test which will read 10 multiple choice questions from a file, order them randomly and provide the test to the user. When the user done the program must give the user his final score
CODE MUST BE IN C++ (please use for loop) write a program that loops a number...
CODE MUST BE IN C++ (please use for loop) write a program that loops a number from 1 to 10 thousand and keeps updating a count variable (count variable starts at 0 ) according to these rules: n1 = 14 n2 = 54 n3 = 123 if the number is divisible by n1, increase count by 1 if the number is divisible by n2, increase count by 2 if the number is divisible by n3, increase count by 3 if...
Please code C# 8. Write a program that prompts the user to enter an integer. The...
Please code C# 8. Write a program that prompts the user to enter an integer. The program then determines and displays the following: Whether the integer is divisible by 5 and 6 Whether the integer is divisible by 5 or 6
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT