This requires the use of C++. The files above make up a utility for generating i
ID: 3588464 • Letter: T
Question
This requires the use of C++.
The files above make up a utility for generating inputs for algorithms. This particular one generates list of N random numbers that are sorted.
The main function declares an array of a number of elements and calls the efficientRandomSortedList function to populate the array with random integers, with the condition that the numbers are sorted. It uses the TimeSupport.h library to keep track of the running time of the generating function.
The generating function itself is defined in DataGen.h. The current version uses the RandomSupport.h library to generate as many random integers as needed, and then uses insertion_sort to sort the list and produce the desired output.
The Compass system has a time limit of 5 seconds for your programs to run. If your program has not completed within that time, it will be terminated.
If the size of the array is small enough, the algorithm in DataGen.h will manage to complete in under 5 seconds, but for larger lists, we need more efficient algorithms.
Given the files below, modify the efficientRandomSortedList function, in DataGen.h to be able to generate 15000000 random numbers (with no repeats) in sorted order, within the 5 second time limit. Test your function by modifying the list size in the dataGen.cpp file to 15000000.
I want to replace the insertion_sort algorithm with QuickSort in order to quickly handle 15000000 random numbers. How do I do that with the given code below?
dalaGeni - Microsoft Visusl 5tudio Express 2012 for Winduws Deskiop Quick Launch (Cti+o IL[ CDIT ViLW PROJECT BUILD DLDLIG TLAM TCOLS TLST WINDOW HELP o , o TB e-" .. Local windows Debugger , Debug win32 TimeSuapor.h andomSupport. DataGon.h Solution Explerer Global Scope) O displaylong listu long s A simple function for displaying the contents of an array Sesch 5olution Explorer (Cl void display(long list[], long s) for (long i =0; iExplanation / Answer
Here is the code for quick sort
// swap two elements
void swap(long* a, long* b)
{
long 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 */
long partition (long arr[], long low, long high)
{
long pivot = arr[high]; // pivot
long i = (low - 1); // Index of smaller element
long j;
for (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 function that implements QuickSort
void quickSort(long arr[], long low, long high)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
long pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
Inside efficientRandomSortedList at line insertion_sort(temp,s) replace it with quicksort(temp, 0, s-1);
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.