C or C++ Please!! 2. Empirical Analysis of Algorithm using C (50 pts) Taskl: Stu

Question

C or C++ Please!!

2. Empirical Analysis of Algorithm using C (50 pts) Taskl: Study the time complexity of Quick Sort using different input size: 10, 100, 1000, 10000, and 100000 (the number of unsorted float-point numbers). (35 pts) Requirements: Write a C can use any uniform random number generator to create an input file. code that randomly generates 100 input files for each input size. You For each input file, run QuickSort and record the execution time. Create an ASCII file, named "yourLastname yourFirstname_execution Time.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 "yourL astname yourFirstname averageExecution Time.txt" containing a table with the average execution times for each input size, such as Input Size 10 100 1000 10000 100000 Average Execution Time 2e-09 4e-09 Task2: Show the average running times in a plot, where x axis represents the input size and the y 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

Here is the complete code for task one

#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 C
• Subjects

---

---

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