PLEASE CODE IN C!! 2. Empirical Analysis of Algorithm using C (50 pts) Taskl: St

Question

PLEASE CODE IN C!!

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

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

// A utility function to swap two elements
void swap(float* a, float* b)
{
float 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 (float 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);
}

/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(float 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);
}
}

/* Function to print an array */
void printArray(float arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%.2f ", arr[i]);
printf(" ");
}

int readInput(const char *file, float *arr) {
FILE* f=NULL;
float num;
f=fopen(file,"r");

int size = 0;
while(!feof(f)){
fscanf(f, "%f", &num);
arr[size] = num;
size++;
}
fclose(f);
return size;
}

void writeOutput(const char *file, float *arr, int size) {
FILE* f=NULL;
float num;
f=fopen(file,"w");
int i;
for(i=0; i<size; i++) {
fprintf(f, "%.2f ", arr[i]);
}
  
fclose(f);
}

// Driver program to test above functions
int main(int argc, char const *argv[]){

float arr[200]; // declaring an array

int n = readInput(argv[1], arr);
quickSort(arr, 0, n-1);
printf("Sorted array: ");
printArray(arr, n);
writeOutput(argv[2], arr, n);

printf("Sorted output successfully written to file ");
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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