2. Empirical Analysis of Algorithm using C or C++. (50 pts) Taskl: Study the tim

Question

2. Empirical Analysis of Algorithm using C or C++. (50 pts) Taskl: Study the time complexity of QuickSort using different input size: 10, 100, 1000, 10000 and 100000 (the number of unsorted float-point numbers). (35 pts) Requirements: Write a C or C+++ code that randomly generates 100 input files for each input size. You can use any uniform random number generator to create an input file . For each input file, run QuickSort and record the execution time. Create an ASCII file, named "yourLastname yourFirstname_executionTime.txt" containing a table with all the execution times, such as: Input Size 10 10 Execution Time 4e-09 3e-09 100 100 Compute the average running time for each input size. Create an ASCII file, named "yourLastname_yourFirstname_averageExecutionTime.txt" containing a table with the average execution times for each input size, such as ut Size 10 100 1000 Average Execution Time 2e-09 4e-09 10000 Task2: Show the average running times in a plot, where x axis represents the input size and they axis represents the time. You will have a curve for QuickSort, where a point on the curve representing the average running time for an input size. Save the plot into a file named "yourLastname_yourFirstname_plotAverageExecutionTime.jpg". (15 pts)

Explanation / Answer

#include <ctime>
#include <cstdlib>
#include <fstream>
#include <iostream>

/* C implementation QuickSort */
#include<stdio.h>

using namespace std;

// A utility function to swap two elements
void swap(int* a, int* b)
{
   int t = *a;
   *a = *b;
   *b = t;
}

/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
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
       if (arr[j] <= pivot)
       {
           i++;    // increment index of smaller element
           swap(&arr[i], &arr[j]);
       }
   }
   swap(&arr[i + 1], &arr[high]);
   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 generateRandomNumbers(int*arr, int j) {

   srand((unsigned)time(0));
   for (int i = 0; i < j; i++)
   {
       arr[i] = rand();
   }

}

// Driver program to test above functions
int main()
{
   clock_t start, end;
   double msecs, avgmsecs;
   ofstream outfile, avgoutfile;
   outfile.open("lastname_firstname_executiontime.txt");
   avgoutfile.open("lastname_firstname_averageExecutiontime.txt");

   outfile << "input size               execution time(in millisecs)" << endl;

   avgoutfile << "input size               average execution time(in millisecs)" << endl;

   for (int j = 10; j < 100001; j = j * 10)
   {
       avgmsecs = 0;

       for (int i = 0; i < 100; i++)
       {
           int* arr = new int[j];

           generateRandomNumbers(arr, j);
           start = clock();

           quickSort(arr, 0, j - 1);

           end = clock();
           msecs = ((double)(end - start)) * 1000 / CLOCKS_PER_SEC;

           outfile << " " << j << "                   " << msecs << endl;

           avgmsecs += msecs;
       }
       avgoutfile << " " << j << "                   " << avgmsecs << endl;
   }

   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

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