Rewrite the following code to sort a list of elements, while not using generic f

Question

Rewrite the following code to sort a list of elements, while not using generic functions such as sort(), inplace_merge(), merge() or copy(). As well it should not use Nodes.

#include <iostream>
#include <vector>
#include <iterator>

using namespace std;

template<class Itr>
void inplaceMerge(Itr low, Itr mid, Itr high)
{
   int dist = high - low;
   vector<typename iterator_traits<Itr>::value_type> temp(dist);
   Itr i = low;
   Itr j = mid;
   Itr k = temp.begin();

   while (i < mid && j < high)
       if (*i < *j)
           *k++ = *i++;
       else
           *k++ = *j++;
   while (i < mid)
       *k++ = *i++;
   while (j < high)
       *k++ = *j++;

   for (k = temp.begin(), i = low; k != temp.end(); k++, i++)
       *i = *k;
} // inplaceMerge
      

template <class Itr>
void m_sort(Itr start, unsigned int low, unsigned int high)
{
   if (low + 1 < high) {
       unsigned int center = (low + high) / 2;
       m_sort(start, low, center);
       m_sort(start, center, high);
       inplaceMerge(start+low, start+center, start+high);
   }
} // m_sort

template <class T>
void mergeSort(vector<T> & s)
{
   m_sort(s.begin(), 0, s.size());
} // mergeSort

main()
{
   vector<int> v;
   int temp;

   while (cin >> temp)
       v.push_back(temp);

   mergeSort(v);

   for (int i = 0; i < v.size(); i++)
       cout << v[i] << ' ';
   cout << endl;
} // main

Explanation / Answer

#include <iostream>
#include <vector>
#include <iterator>

using namespace std;

template<class Itr>
void inplaceMerge(Itr low, Itr mid, Itr high)
{
    int dist = high - low;
    vector<typename iterator_traits<Itr>::value_type> temp(dist);
    Itr i = low;
    Itr j = mid;
    Itr k = temp.begin();

    while (i < mid && j < high)
        if (*i < *j)
            *k++ = *i++;
        else
            *k++ = *j++;
    while (i < mid)
        *k++ = *i++;
    while (j < high)
        *k++ = *j++;

    for (k = temp.begin(), i = low; k != temp.end(); k++, i++)
        *i = *k;
} // inplaceMerge
      

template <class Itr>
void m_sort(Itr start, unsigned int low, unsigned int high)
{
    if (low + 1 < high) {
        unsigned int center = (low + high) / 2;
        m_sort(start, low, center);
        m_sort(start, center, high);
        inplaceMerge(start+low, start+center, start+high);
    }
} // m_sort

template <class T>
void mergeSort(vector<T> & s)
{
    m_sort(s.begin(), 0, s.size());
} // mergeSort

main()
{
    vector<int> v;
    int temp,i,k;

    while (cin >> temp)
    {    v.push_back(temp);
       i = v.size()-1;
       //sorting here..insertion sort
       while(i>=1)
       {
           if(v[i]<v[i-1])//placing in correct position
           {
               k=v[i];//swapping
               v[i]=v[i-1];
               v[i-1]=k;
           }
           else break;
           i--;      
         }
       ///  
   }

    //mergeSort(v);

    for (int i = 0; i < v.size(); i++)
        cout << v[i] << ' ';
    cout << endl;
} // main

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

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