This requires the use of C++. The files above make up a utility for generating i

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 MergeSort 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 v TimeSuapor.h andomSupport. Dat Gen.h"× dataGcn.c Solution Explerer Global Scope) void insertion-sort(long long n size; for ( long i 1; i && list [j-1] > list[j]){ External Dezendencies Header Files long temp listj]; ist[]-list[-1; list[j-1]-temp; stdafsh targetve.h Resource Files daaGer.cpp ReadMe.txt void efficientRandomSortedList(long temp long s) Sclutio... Team E Class Get a new random device randomizer device new_randomizer) Properies Get a uniform distribution from 1 to 188e uniform_distribution rangenew distribution(1, 15000eae); for (long i = 0; i s; // At every cell of the array, insert a randomly selected number from temp[1] distribution defined above = sample(range, device); Now sort the array using insertion_sort insertion_sort(temp,s); 124 % Eror List Cutout 8:56 AM Type here to search 1/62017

Explanation / Answer

You can try this 2 function to change insertion to mergesort.

mearg_sort function from main function with array address ,starting subaddress , and ending address -1.

ex - merge(list,0,size-1)

where size = size of array.

// Merges two subarrays of list[].
// First subarray is list[l..m]
// Second subarray is list[m+1..r]
void merge(long list[], long l, long m, long r)
{
long i, j, k;
long n1 = m - l + 1;
long n2 = r - m;

/* create temp arrays */
long L[n1], R[n2];

/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = list[l + i];
for (j = 0; j < n2; j++)
R[j] = list[m + 1+ j];

/* Merge the temp arrays back into list[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
list[k] = L[i];
i++;
}
else
{
list[k] = R[j];
j++;
}
k++;
}

/* Copy the remaining elements of L[], if there
are any */
while (i < n1)
{
list[k] = L[i];
i++;
k++;
}

/* Copy the remaining elements of R[], if there
are any */
while (j < n2)
{
list[k] = R[j];
j++;
k++;
}
}

/* l is for left index and r is right index of the
sub-array of list to be sorted */
void merge_sort(long list[],long l, long r)
{
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
long m = l+(r-l)/2;

// Sort first and second halves
merge_sort(list, l, m);
merge_sort(list, m+1, r);

merge(list, l, m, r);
}
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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