Hi. I am struggling to implement merge sort (C++) non recursively. I understand

Question

Hi. I am struggling to implement merge sort (C++) non recursively. I understand the concept of splitting into subarrays and sort and merging, but can't seem to put the proper program together. I need the first function, subarrayMerge where the actual comparing and sorting takes place.

#include

#include

#include

#include

using namespace std;

/*

* template

* void mergesortDecreasing(vector & a)

* Implement this function which sorts the elements in a vector

* in descending order.

* Implement merge sort using a NONRECURSIVE approach. This is

* accomplished using a "bottom up" approach: first every pair

* of successive elements are sorted. Then each pair of sorted

* pairs are merged, followed by merging lists of length 4, 8,

* ... until the entire list is sorted.

*

* Hints:

* - Implement a helper function that merges sorted subarrays of

* the array, taking indices of different subarrays as input.

* - Merge sorted lists in a temporary array and then copy the

* results back into the main array.

* - Make sure to deal with input of length that is not an even

* power of two.

*/

template

void subarrayMerge(int first, int last, int mid, vector & temp, vector & a){

}

template

void mergesortDecreasing(vector & a){

   vector<Comparable> temp(a.size());

   int left, right, mid, sub;

   for (sub = 1; sub < a.size(); sub = 2*sub){

       for (int i = 0; i < a.size(); i = i + 2*sub){

           left = i;

           mid = i + sub;

           right = i + 2*sub;

           subarrayMerge(left, right, mid, temp, a);

       }

   }

}

template

void printVector(string label, vector & a)

{

   cout << label << ": ";

   for (unsigned i = 0; i < a.size(); i++) {

       cout << a[i] << " ";

   }

   cout << endl;

}

void sortRandomIntegers(int number)

{

   vector a(number);

   for (unsigned i = 0; i < a.size(); i++) {

       int num = rand() % 1000;

       a[i] = num;

   }

   printVector(" Input",a);

   mergesortDecreasing(a);

   printVector("Sorted",a);

   cout << endl;

}

void sortRandomDoubles(int number) {

   vector a(number);

   for (unsigned i = 0; i < a.size(); i++) {

       double val = ((double)(rand() % 100000))/33452.0 - 1.0;

       a[i] = val;

   }

   printVector(" Input",a);

   mergesortDecreasing(a);

   printVector("Sorted",a);

   cout << endl;

}

int main() {

   srand(time(NULL));

   sortRandomIntegers(16);

   sortRandomIntegers(17);

   sortRandomIntegers(20);

   sortRandomIntegers(21);

   sortRandomIntegers(289);

   sortRandomDoubles(7);

   sortRandomDoubles(8);

   sortRandomDoubles(9);

}

Explanation / Answer

Complete Program:

#include <iostream>
#include <vector>
#include <string>
#include <ctime>
using namespace std;

template <class T>
void subarrayMerge(int first, int last, int mid, vector<T> & temp, vector<T> & a)
{
    vector<int> result;

    unsigned p = first, q = mid+1;

    while(p <= mid && q < last)
    {
        if(a[p] > temp[q])
        {
            result.push_back(a[p]);
            p++;
        }
        else
        {
            result.push_back(temp[q]);
            q++;
        }
    }

    while(p <= mid)
    {
        result.push_back(a[p]);
        p++;
    }

    while(q < last)
    {
        result.push_back(temp[q]);
        q++;
    }

for(unsigned i = 0; i < result.size(); i++)
  a[i] = result[i];
}

template <class T>
void mergesortDecreasing(vector<T> & a)
{
//vector<Comparable> temp(a.size());
vector<T> temp(a.size());

int left, right, mid, sub;

for (sub = 1; sub < a.size(); sub = 2*sub)
{
  for (int i = 0; i < a.size(); i = i + 2*sub)
  {
   left = i;
   mid = i + sub;
   right = i + 2*sub;
   subarrayMerge(left, right, mid, temp, a);
  }
}
}

template <class T>
void printVector(string label, vector<T> & a)
{
cout << label << ": ";
for (unsigned i = 0; i < a.size(); i++)
{
  cout << a[i] << " ";
}
cout << endl;
}

void sortRandomIntegers(int number)
{
vector<int> a(number);

for (unsigned i = 0; i < a.size(); i++)
{
  int num = rand() % 1000;
  a[i] = num;
}

printVector(" Input", a);
mergesortDecreasing(a);
printVector("Sorted",a);
cout << endl;
}

void sortRandomDoubles(int number)
{
vector<double> a(number);

for (unsigned i = 0; i < a.size(); i++)
{
  //double val = ((double)(rand() % 100000))/33452.0 - 1.0;
  double val = 1.0 + ((double)rand() / RAND_MAX * (33452.0 - 1.0));
  a[i] = val;
}

printVector(" Input",a);
mergesortDecreasing(a);
printVector("Sorted",a);
cout << endl;
}

int main()
{
srand(time(NULL));

sortRandomIntegers(16);
sortRandomIntegers(17);
sortRandomIntegers(20);
sortRandomIntegers(21);
sortRandomIntegers(289);
sortRandomDoubles(7);
sortRandomDoubles(8);
sortRandomDoubles(9);

system("pause");
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

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