Please Code in C

The merge sort algorithm recursively divides the array in half until an array with one element is reached. A variant of merge sort, called natural merge sort, instead finds already-sorted runs of elements and merges the runs together.

Step 1: Implement the GetSortedRunLength() member function

Implement the GetSortedRunLength() member function in NaturalMergeSorter.h. Access NaturalMergeSorter.h by clicking on the orange arrow next to main.cpp at the top of the coding window.

GetSortedRunLength() has three parameters:

array: a pointer to an array of integers,

arrayLength: an integer for the array's length, and

startIndex: an integer for the run's starting index.

The function returns the number of array elements sorted in ascending order, starting at startIndex and ending either at the end of the sorted run, or the end of the array, whichever comes first. The function returns 0 if startIndex is out of bounds.

File main.cpp has several test cases for GetSortedRunLength() that can be run by clicking the "Run program" button. One test case also exists for NaturalMergeSort(), but that can be ignored until step two is completed.

The program's output does not affect grading.

Submit for grading to ensure that the GetSortedRunLength() unit tests pass before proceeding.

Step 2: Implement the NaturalMergeSort() member function

Implement the NaturalMergeSort() member function in NaturalMergeSorter.h. NaturalMergeSort() must:

1. Start at index i=0

2. Get the length of the first sorted run, starting at i

Return if the first run's length equals the array length

If the first run ends at the array's end, reassign i=0 and repeat step 2

3. Get the length of the second sorted run, starting immediately after the first

4. Merge the two runs with the provided Merge() function

5. Reassign i with the first index after the second run, or 0 if the second run ends at the array's end

6. Go to step 2

MAIN.CPP (Read Only)

#include #include #include "NaturalMergeSorter.h" #include "RunLengthTestCase.h" using namespace std;

bool IsArraySorted(int* arr, int arrSize); void WriteArray(int* array, int arrayLength);

int main(int argc, char *argv[]) { // Test case array: A completely sorted array int arr1[] = { 15, 23, 23, 23, 31, 64, 77, 87, 88, 91 }; int arr1Length = sizeof(arr1) / sizeof(arr1[0]);

// Test case array: Sorted run of 3 followed by sorted run of 6 int arr2[] = { 64, 88, 91, 12, 21, 34, 43, 56, 65 }; int arr2Length = sizeof(arr2) / sizeof(arr2[0]);

// Test case array: 5 elements in descending order, so 5 runs of length 1 int arr3[] = { -10, -20, -30, -40, -50 }; int arr3Length = sizeof(arr3) / sizeof(arr3[0]);

// Test case array: 8 equal elements, so 1 run of 8 int arr4[] = { -99, -99, -99, -99, -99, -99, -99, -99 }; int arr4Length = sizeof(arr4) / sizeof(arr4[0]);

// Test cases: RunLengthTestCase testCases[] = { // First test case uses an out-of-bounds starting index. Remaining test // cases do not. RunLengthTestCase(arr1, arr1Length, arr1Length, 0), RunLengthTestCase(arr1, arr1Length, 0, arr1Length), RunLengthTestCase(arr1, arr1Length, 3, arr1Length - 3), RunLengthTestCase(arr2, arr2Length, 0, 3), RunLengthTestCase(arr2, arr2Length, 2, 1), RunLengthTestCase(arr2, arr2Length, 3, 6), RunLengthTestCase(arr3, arr3Length, 0, 1), RunLengthTestCase(arr3, arr3Length, 3, 1), RunLengthTestCase(arr4, arr4Length, 0, arr4Length), RunLengthTestCase(arr4, arr4Length, 4, arr4Length - 4), RunLengthTestCase(arr4, arr4Length, 5, arr4Length - 5) };

// Execute each test case int testCasesLength = sizeof(testCases) / sizeof(testCases[0]); for (int i = 0; i < testCasesLength; i++) { RunLengthTestCase& testCase = testCases[i];

// Execute the test case, using std::cout to write messages testCase.Execute(std::cout); }

// Test case array for sorting int arr5[] = { 92, 71, 18, 26, 54, 73, 89, 10, 39, 99, 64, 22 }; int arr5Length = sizeof(arr5) / sizeof(arr5[0]); int* arr5Copy = new int[arr5Length]; for (int i = 0; i < arr5Length; i++) { arr5Copy[i] = arr5[i]; }

NaturalMergeSorter sorter; sorter.NaturalMergeSort(arr5Copy, arr5Length); cout << endl; cout << (IsArraySorted(arr5Copy, arr5Length) ? "PASS" : "FAIL"); cout << ": NaturalMergeSort()" << endl; cout << " Array before calling NaturalMergeSort(): ["; WriteArray(arr5, arr5Length); cout << "]" << endl; cout << " Array after calling NaturalMergeSort(): ["; WriteArray(arr5Copy, arr5Length); cout << "]" << endl; delete[] arr5Copy;

return 0; }

bool IsArraySorted(int* arr, int arrSize) { for (int i = 1; i < arrSize; i++) { if (arr[i] < arr[i - 1]) { return false; } } return true; }

void WriteArray(int* array, int arrayLength) { // Output occurs only if at least one array element exists if (arrayLength > 0) { // Write the first element without a comma cout << array[0];

// Write each remaining element preceded by a comma for (int i = 1; i < arrayLength; i++) { cout << ", " << array[i]; } } }

-------------------------------------------------------------------------------------------------------------------

RunLengthTestCase.h (Read Only)

#ifndef RUNLENGTHTESTCASE_H #define RUNLENGTHTESTCASE_H

#include #include "NaturalMergeSorter.h"

// RunLengthTestCase represents a test case for the NaturalMergeSorter class's // GetSortedRunLength() function. class RunLengthTestCase { public: int* array; int arrayLength; int startIndex; int expectedReturnValue; RunLengthTestCase(int* array, int len, int start, int expectedRet) { this->array = array; arrayLength = len; startIndex = start; expectedReturnValue = expectedRet; } // Executes the test case. If the test case passes, a message that starts // with "PASS" is printed and true is returned. Otherwise a message that // starts with "FAIL" is printed and false is returned. bool Execute(std::ostream& testFeedback) { using namespace std; // Create a NaturalMergeSorter instance NaturalMergeSorter userSorter; // Call the GetSortedRunLength() function with the test case parameters int userRetVal = userSorter.GetSortedRunLength( array, arrayLength, startIndex); // The test passed only if the actual return value equals the expected // return value const bool passed = (userRetVal == expectedReturnValue); // Show a message about the test case's results testFeedback << (passed ? "PASS: " : "FAIL: "); testFeedback << "GetSortedRunLength()" << endl; testFeedback << " Array: ["; WriteArray(testFeedback); testFeedback << "]" << endl; testFeedback << " Start index: " << startIndex << endl; testFeedback << " Expected return value: " << expectedReturnValue; testFeedback << endl; testFeedback << " Actual return value: " << userRetVal << endl; return passed; } // Writes comma-separated elements to the output stream void WriteArray(std::ostream& output) const { // Output occurs only if at least one array element exists if (arrayLength > 0) { // Write the first element without a comma output << array[0]; // Write each remaining element preceded by a comma for (int i = 1; i < arrayLength; i++) { output << ", " << array[i]; } } } };

#endif

-------------------------------------------------------------------------------------------------------------------

NaturalMergeSorter.h (Edit in this file)

#ifndef NATURALMERGESORTER_H #define NATURALMERGESORTER_H

class NaturalMergeSorter { public: virtual int GetSortedRunLength(int* array, int arrayLength, int startIndex) { // Your code here } virtual void NaturalMergeSort(int* array, int arrayLength) { // Your code here } virtual void Merge(int* numbers, int leftFirst, int leftLast, int rightLast) { int mergedSize = rightLast - leftFirst + 1; int* mergedNumbers = new int[mergedSize]; int mergePos = 0; int leftPos = leftFirst; int rightPos = leftLast + 1; // Add smallest element from left or right partition to merged numbers while (leftPos <= leftLast && rightPos <= rightLast) { if (numbers[leftPos] <= numbers[rightPos]) { mergedNumbers[mergePos] = numbers[leftPos]; leftPos++; } else { mergedNumbers[mergePos] = numbers[rightPos]; rightPos++; } mergePos++; } // If left partition isn't empty, add remaining elements to mergedNumbers while (leftPos <= leftLast) { mergedNumbers[mergePos] = numbers[leftPos]; leftPos++; mergePos++; } // If right partition isn't empty, add remaining elements to mergedNumbers while (rightPos <= rightLast) { mergedNumbers[mergePos] = numbers[rightPos]; rightPos++; mergePos++; } // Copy merged numbers back to numbers for (mergePos = 0; mergePos < mergedSize; mergePos++) { numbers[leftFirst + mergePos] = mergedNumbers[mergePos]; } // Free temporary array delete[] mergedNumbers; } };

#endif