Untitled
unknown
plain_text
3 years ago
2.2 kB
4
Indexable
void merge(int *arr, const int size, int &compCount, int &moveCount, int first, int mid, int last){ int *tempArray = new int[size]; // Determine the first, mid, and the last values int first1 = first; int last1 = mid; int first2 = mid + 1; int last2 = last; int index = first1; // Compare each element and start to fill array while( ( first1 <= last1) && ( first2 <= last2 ) ){ if( arr[first1] < arr[first2] ){ tempArray[index] = arr[first1]; first1++; } else{ tempArray[index] = arr[first2]; first2++; } compCount++; moveCount++; index++; } // Finish to fill the array with one of halves while( ( first1 <= last1) ){ tempArray[index] = arr[first1]; moveCount++; index++; first1++; } while( ( first2 <= last2) ){ tempArray[index] = arr[first2]; moveCount++; index++; first2++; } // Copy the temp array into the real array for ( index = first; index <= last; index++){ arr[index] = tempArray[index]; moveCount++; } // Delete the temp array delete [] tempArray; } /* * Overloaded function of mergeSort * Has 2 extra parameters which is first and last index of the array */ void mergeSort(int *arr, const int size, int &compCount, int &moveCount, int first, int last){ if ( first < last ) { int mid = (first + last)/2; mergeSort(arr, size, compCount, moveCount, first, mid); // Sort the first half mergeSort(arr, size, compCount, moveCount, mid + 1, last); // Sort the second half // Merge the two halves merge(arr, size, compCount, moveCount, first, mid, last); } } void mergeSort(int *arr, const int size, int &compCount, int &moveCount){ // Call the overloaded function of mergeSort to be able to add 2 extra parameter mergeSort( arr, size, compCount, moveCount, 0, size - 1); // First index is zero, last index is (size - 1) }
Editor is loading...