Using C++, I\'ve been trying to create this code to perform a mergesort. I have

Question

Using C++, I've been trying to create this code to perform a mergesort. I have created an array of 10,000 elements and filled it with random numbers. I then implemented a mergesort function and merge function. I know there are mistakes in this section but I don't know what exactly. I then implemented a timesort function to try and determine the time it takes to perform the mergesort function. Again, in know there is a mistake when calling the mergesort function in this section and I don't know how to fix it. Lastly, in my main function, I want to display the unsorted array, the sorted array after the mergesort, and the time it took to perform the mergesort at 10,000 elements, 20,000 elements, 30,000 elements, and 40,000 elements. Please help me fix my code!

#include <iostream> // Used for input and output.
#include <conio.h>
#include <cstdlib>
#include <time.h>

using namespace std;

// Press any key to continue.
void pressAnyKey()
{
cout << "Press any key to continue" << endl;
_getch();     // Waits and gets next character entered.
}

// Display values of array - each on their own line.
void displayArray(int array[], int length)
{
int i = 0;
while (i < length)
{
  cout << array[i] << " ";
  i++;
}
cout << endl;
}

// Give a random value to each element of the array.
void randomizeArray(int array[], int length)
{
srand((unsigned)time(NULL));   // Seed random number generator.

int i = 0;
do
{
  array[i] = rand() % 1000000 + 1;  // A random number in the range of 1 to 100,000 is assigned.
  i++;
} while (i < length);
}

// Sort array.

void merge(int*, int, int, int);
void mergesort(int*, int, int);
void timeSort(int array[], int length);

void mergesort(int *array, int left, int right)
{
int mid;
if (left < right)
{
  mid = (left + right) / 2;
  mergesort(array, left, mid);
  mergesort(array, mid + 1, right);
  merge(array, left, right, mid);
  displayArray;
}
}

void merge(int *array, int left, int right, int mid)
{
int firsthalfindex, secondhalfindex, outputindex, output[10000];

firsthalfindex = left;
secondhalfindex = mid + 1;
outputindex = left;

while (firsthalfindex <= mid && secondhalfindex <= right)
{
  if (array[firsthalfindex] < array[secondhalfindex])
  {
   output[outputindex] = array[firsthalfindex];

   outputindex++;
   firsthalfindex++;
  }
  else
  {
   output[outputindex] = array[secondhalfindex];

   outputindex++;
   secondhalfindex++;
  }
}
while (firsthalfindex <= mid) {
  output[outputindex] = array[firsthalfindex];

  outputindex++;
  firsthalfindex++;
}
while (secondhalfindex <= mid)
{
  output[outputindex] = array[secondhalfindex];
  outputindex++;
  secondhalfindex++;
}
for (firsthalfindex = left; firsthalfindex < outputindex; firsthalfindex++)
{
  array[firsthalfindex] = output[firsthalfindex];
}

}

void timeSort(int array[], int length)
{
clock_t startTime, endTime;
// Randomize values in array.
randomizeArray(array, length);

// Time array sort.
startTime = clock();   // Get starting time.
mergesort(array, length); // Sort array.
endTime = clock();    // Get ending time.

         // Display algorithm's running time as difference between starting and ending time.
cout << "Mergesort time for an array of "
  << length
  << ": "
  << ((float)endTime - (float)startTime) / CLOCKS_PER_SEC * 1000
  << " milliseconds." // On my machine, CLOCKS_PER_SEC is equal to 1000 and
       // thus milliseconds is the correct unit.
  << endl;
}

int main()
{
const int length = 10000;  // The base length of our test arrays.

int demo[length];
displayArray(demo, length);

randomizeArray(demo, length); // Randomize values in array and display.
displayArray(demo, length);
pressAnyKey();

mergesort(demo, length);
// Test 1: Time and sort array.
int test1[length];
timeSort(test1, length);

// Test 2: Time and sort array.
int test2[2 * length];
timeSort(test2, 2 * length);

// Test 3: Time and sort array.
int test3[3 * length];
timeSort(test3, 3 * length);

// Test 4: Time and sort array.
int test4[4 * length];
timeSort(test4, 4 * length);

// End program.
pressAnyKey();
return 0;

}

Explanation / Answer

I did some changes in your code, check the code below.

Segmentation fault will come for higer no i.e 10000, as it will be out of the memory so I changed in your code 1500 elements.

Check the comments wherever changed. Search for "Chegg comment"

#include <iostream> // Used for input and output.
#include <conio.h>
#include <cstdlib>
#include <time.h>

using namespace std;

// Press any key to continue.
void pressAnyKey()
{
cout << "Press any key to continue" << endl;
getch(); // Waits and gets next character entered. // Chegg comment: getch() is used
}
// Display values of array - each on their own line.
void displayArray(int array[], int length)
{
int i = 0;
while (i < length)
{
cout << array[i] << " ";
i++;
}
cout << endl;
}
// Give a random value to each element of the array.
void randomizeArray(int array[], int length)
{
srand((unsigned)time(NULL)); // Seed random number generator.
int i = 0;
do
{
array[i] = rand() % 1000000 + 1; // A random number in the range of 1 to 100,000 is assigned.
i++;
} while (i < length);
}
// Sort array.
void merge(int*, int, int, int);
void mergesort(int*, int, int);
void timeSort(int array[], int length);
void mergesort(int *array, int left, int right)
{
int mid;
if (left < right)
{
//mid = (left + right) / 2; // Chegg comment: Re-write this for avoiding segmentation fault
mid = left + (right - left)/2;
mergesort(array, left, mid);
mergesort(array, mid + 1, right);
merge(array, left, right, mid);
//displayArray; // Chegg comment: Wrongly put here
}
}
void merge(int *array, int left, int right, int mid)
{
int firsthalfindex, secondhalfindex, outputindex, output[10000];
firsthalfindex = left;
secondhalfindex = mid + 1;
outputindex = left;
while (firsthalfindex <= mid && secondhalfindex <= right)
{
if (array[firsthalfindex] < array[secondhalfindex])
{
output[outputindex] = array[firsthalfindex];
outputindex++;
firsthalfindex++;
}
else
{
output[outputindex] = array[secondhalfindex];
outputindex++;
secondhalfindex++;
}
}
while (firsthalfindex <= mid) {
output[outputindex] = array[firsthalfindex];
outputindex++;
firsthalfindex++;
}
while (secondhalfindex <= mid)
{
output[outputindex] = array[secondhalfindex];
outputindex++;
secondhalfindex++;
}
for (firsthalfindex = left; firsthalfindex < outputindex; firsthalfindex++)
{
array[firsthalfindex] = output[firsthalfindex];
}
}

void timeSort(int array[], int length)
{
clock_t startTime, endTime;
// Randomize values in array.
randomizeArray(array, length);
// Time array sort.
startTime = clock(); // Get starting time.
mergesort(array, 0, length); // Sort array. // Chegg comment: left is missing
endTime = clock(); // Get ending time.
// Display algorithm's running time as difference between starting and ending time.
cout << "Mergesort time for an array of "
<< length
<< ": "
<< ((float)endTime - (float)startTime) / CLOCKS_PER_SEC * 1000
<< " milliseconds." // On my machine, CLOCKS_PER_SEC is equal to 1000 and
// thus milliseconds is the correct unit.
<< endl;
}
int main()
{
const int length = 1500; // The base length of our test arrays. // Chegg comment: Segmentation fault is coming due to lower RAM, decrease based on your RAM
int demo[length];
//displayArray(demo, length);// Chegg comment: No need of this as it will show all 0

randomizeArray(demo, length); // Randomize values in array and display.
displayArray(demo, length);
pressAnyKey();

mergesort(demo, 0, length);
displayArray(demo, length); // Chegg comment: Added here for displaying the array after sorting
// Test 1: Time and sort array.
int test1[length];
timeSort(test1, length);
// Test 2: Time and sort array.
int test2[2 * length];
timeSort(test2, 2 * length);
// Test 3: Time and sort array.
int test3[3 * length];
timeSort(test3, 3 * length);
// Test 4: Time and sort array.
int test4[4 * length];
timeSort(test4, 4 * length);
// End program.
pressAnyKey();
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

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