This requires the use of C++. The files above make up a utility for generating i
ID: 3587594 • 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.
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
Just replace your insertion_sort() function with the merge_sort() and merge() function given below:
//Also to call it in effecientRandomSortedList-----------------> merge_sort(temp,0,s-1);
//and include this header as well --------------------------------> #include<limits>
void merge(long list[], long initial, long middle, long end) //merge function actually sorts the arrays
{
long max=numeric_limits<int> ::max();
long i, j;
long nleft = middle - initial + 1;
long nright = end - middle;
long left[nleft+1],right[nright+1];
for (i = 0; i < nleft; i++)
left[i] = list[i + initial];
for (i = 0; i < nright; i++)
right[i] = list[i + middle+1];//i+nleft+initial-1
left[nleft] = max;//for all values of a negligible to left[nleft+1]
right[nright] = max;
for (long k = initial, i = 0, j = 0; k <= end; k++)
{
if (left[i] <= right[j])
{
list[k] = left[i];
i++;
}
else
{
list[k] = right[j];
j++;
}
}
}
void merge_sort(long list[],long initial, long end) //merge sort function
{
long middle;
if (initial < end)
{
middle = (initial + end) / 2;
merge_sort(list,initial, middle); //recursive call to divide into left
merge_sort(list,middle + 1, end); //and right array
merge(list,initial, middle, end); //merge function to sort them in steps
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.