Answered step by step
Verified Expert Solution
Question
1 Approved Answer
data structures 3 . 1 6 LAB: Natural merge sort The merge sort algorithm recursively divides the array in half until an array with one
data structures LAB: Natural merge sort
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 alreadysorted runs of elements and merges the runs together.
Ex: The unsorted array below has five sorted runs.
Array with contents Five runs are color coded. Indices and comprise run A shown in red. Indices and comprise run B shown in yellow. Index comprises run C shown in green. Indices and comprise run D shown in blue. Index comprises run E shown in purple.
Natural merge sort starts at index and finds sorted runs A and B Runs A and B are merged, using the same merging algorithm as merge sort, to make run F
Array with contents Four runs are color coded. Indices and comprise run F shown in red. Index comprises run C shown in green. Indices and comprise run D shown in blue. Index comprises run E shown in purple.
Next, the algorithm starts after the merged part F again looking for two sequential, sorted runs. Runs C and D are found and merged to make run G
Array with contents Three runs are color coded. Indices and comprise run F shown in red. Indices and comprise run G shown in blue. Index comprises run E shown in purple.
The algorithm then starts after the merged portion G Only one run exists, run E until the end of the array is reached. So the algorithm starts back at index finds runs F and G and merges to make run H
Array with contents Two runs are color coded. Indices and comprise run H shown in red. Index comprises run E shown in purple.
Again a single run is found after the justmerged part, so the search starts back at index Runs H and E are found and merged.
One last search for a sorted run occurs, finding a sorted run length equal to the array's length. So the array is sorted and the algorithm terminates.
Sorted array with contents
Step : 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 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 : Implement the NaturalMergeSort member function
Implement the NaturalMergeSort member function in NaturalMergeSorter.h NaturalMergeSort must:
Start at index i
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 and repeat step
Get the length of the second sorted run, starting immediately after the first
Merge the two runs with the provided Merge function
Reassign i with the first index after the second run, or if the second run ends at the array's end
Go to step some of the code here #ifndef NATURALMERGESORTERH
#define NATURALMERGESORTERH
class NaturalMergeSorter
public:
virtual int GetSortedRunLengthint array, int arrayLength, int startIndex
Your code here
virtual void NaturalMergeSortint array, int arrayLength
Your code here
virtual void Mergeint numbers, int leftFirst, int leftLast,
int rightLast
int mergedSize rightLast leftFirst ;
int mergedNumbers new intmergedSize;
int mergePos ;
int leftPos leftFirst;
int rightPos leftLast ;
Add smallest element from left or right partition to merged numbers
while leftPos leftLast && rightPos rightLast
if numbersleftPos numbersrightPos
mergedNumbersmergePos numbersleftPos;
leftPos;
else
mergedNumbersmergePos numbersrightPos;
rightPos;
mergePos;
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started