Help with this sorting vectors #include <vector> using std::vector; using std::s

Question

 Help with this sorting vectors #include <vector>  using std::vector; using std::swap;  // MergeSort(): sort the values in the data vector using a Merge Sort //   data - vector to be sorted //   first & last - first and last indices to be sorted //      (makes it possible to sort a sub-vector) //   cmp - function to compare a and b.  cmp(a, b) returns  //      -/0/+ as a is less than/equal to/greater than b  template <class T> void MergeSort(vector<T>& data, int first, int last, int (*cmp)(const T& a, const T& b)) {    // Implement merge sort   // May write separate Merge function, or include Merge code in MergeSort  }         // SelectionSort(): sort the values in the data vector using a Selection Sort //   data - vector to be sorted //   first & last - first and last indices to be sorted //      (makes it possible to sort a sub-vector) //   cmp - function to compare a and b.  cmp(a, b) returns  //      -/0/+ as a is less than/equal to/greater than b  template <class T> void SelectionSort(vector<T>& data, int first, int last, int (*cmp)(const T& a, const T& b)) {    // Implement selection sort  }   

Explanation / Answer

Below are your methods

template <class T>
void MergeSort(vector<T>& data, int p, int r, int (*cmp)(const T& a, const T& b)) {
// Implement merge sort
// May write separate Merge function, or include Merge code in MergeSort
// if index is right
if(p < r)
{
// get the mid index
int mid = (p + r) / 2;
// sort the left subarray
MergeSort(data, p, mid, cmp);
// sort the right subarray
MergeSort(data, mid + 1, r, cmp);
// merge the two subarrays
Merge(data, p, mid, r , cmp);
}
}

// merge the two subarray [ p , mid ] and [ nid + 1 , r ]

template <class T>

void Merge(vector<T>& arr, int p, int q, int r, int (*cmp)(const T& a, const T& b))
{
// get the length of left subarray
int n1 = q - p + 1;
// get the length of right subarray
int n2 = r - q;
int i,j,k;
// create two arrays left and right
T *left = new T[n1 + 1];
T *right = new T[n2 + 1];
// fill left with the contents of left subarray of arr
for(i = 0; i < n1; i++)
left[i] = arr[p + i];
// fill right with the contents of right subarray of arr
for(i = 0; i < n2; i++)
right[i] = arr[q + i + 1];
// set the last element to infinity
left[n1] = (T)INT_MAX;
right[n2] = (T)INT_MAX;
i=0;
j=0;
for(k = p ; k <= r; k++)
{
// if the current element of left is smaller than
// current element of right
if( cmp( left[i] , right[j] ) <= 0)
{
arr[k] = left[i];
i++;
}
// if the current element of left is larger than
// current element of right
else
{
arr[k] = right[j];
j++;
}
}
}

// SelectionSort(): sort the values in the data vector using a Selection Sort
// data - vector to be sorted
// first & last - first and last indices to be sorted
// (makes it possible to sort a sub-vector)
// cmp - function to compare a and b. cmp(a, b) returns
// -/0/+ as a is less than/equal to/greater than b

template <class T>
void SelectionSort(vector<T>& data, int first, int last, int (*cmp)(const T& a, const T& b)) {
int i, j, min;
T x;
int n = data.size();
// traverse the array
for (i = 0; i < n - 1; i++)
{
// store the index of the smallest element
min = i;
// traverse the array from the element after i till the end
for (j = i + 1; j < n; j++)
{
// if the current element is smaller than the min element
if(cmp( data[j] , data[min]) < 0 )
min = j;
}
// Swap first element and min
x = data[min];
data[min] = data[i];
data[i] = x;
}
}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

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