Rewrite algorithm as a template function to compare 2 values

Question

1.33/5 (2 votes)

See more:

I am trying to rewrite the selection sort algorithm below as a template function that compares two elements. My original programs does a sort, but I am not sure how to rewrite the program as a function. I can write the function independently, which I did, but I am having trouble rewriting the program.
here is my sorting algorithm

C++

#include <iostream>

#include "util.h"

/** 
    Gets the position of the smallest element in a vector range.
    @param a the vector
    @param from the beginning of the range
    @param to the end of the range
    @return the position of the smallest element in 
    the range a[from]...a[to]
*/
int min_position(vector<int>& a, int from, int to)
{  
   int min_pos = from;
   int i;
   for (i = from + 1; i <= to; i++)
      if (a[i] < a[min_pos]) min_pos = i;
   return min_pos;
}

/** 
   Sorts a vector using the selection sort algorithm
   @param a the vector to sort
*/

void selection_sort(vector<int>& a)
{  
   int next; // The next position to be set to the minimum

   for (next = 0; next < a.size() - 1; next++)
   {  
      // Find the position of the minimum
      int min_pos = min_position(a, next, a.size() - 1);
      if (min_pos != next)
         swap(a[min_pos], a[next]);
   }
}

int main()
{  
   rand_seed();
   vector<int> v(20);
   for (int i = 0; i < v.size(); i++)
      v[i] = rand_int(1, 100);
   print(v);
   selection_sort(v);
   print(v);
   return 0;
}

I wrote a template to compare the values, but I am having trouble implementing it on my program above.

C++

template <typename T>
void sort(T A[],int N)
{

 for(int n = 1;n < N;n++) {
     T mover = A[n];
     int k = n;
     while(k > 0) {
       if(A[k-1] > mover) {
         A[k] = A[k-1];
        k--;
       } else
         break;
     }
     A[k] = mover;
}

}

I am new to c++ and templates/sorting is giving me fits, so I am looking for some assistance/guidance

Thanks

Posted 2-Aug-13 14:39pm

qbndl8

Updated 2-Aug-13 22:12pm

Richard MacCutchan

v2

Add a Solution

Comments

Sergey Alexandrovich Kryukov 2-Aug-13 20:53pm

What trouble, exactly? You cannot get help if you don't provide the explanations of your problems.
—SA

qbndl8 2-Aug-13 21:00pm

Hi Sergey. My trouble is that i do not know how to re write the program as a template. I can write template by itself (which I did on my second code) but i can't implemented on ,my first program

Sergey Alexandrovich Kryukov 2-Aug-13 22:58pm

Do you mean template class? First, you need to learn OOP (in case you are not ready yet) and templates. Why a template by the way? What do you want to abstract out and why?
—SA

Philippe Mori 2-Aug-13 23:27pm

If you can write the first and the second fragment of code, then I think it should not be hard to figure out how to make a Template from first code segment.

2 solutions

Solution 1

Let's try one base on one of Microsoft's examples. Most of the code for what you want to do goes into a header file:

C++

// needed for implementation
// Inline function declarations

#ifdef _AFX_ENABLE_INLINES
#define _AFX_INLINE AFX_INLINE

#if !defined(_AFX_CORE_IMPL) || !defined(_AFXDLL) || defined(_DEBUG)
#define _AFX_PUBLIC_INLINE AFX_INLINE
#else
#define _AFX_PUBLIC_INLINE
#endif
#endif


template<class TYPE, class ARG_TYPE>
class CCuteBundle;

Then below the code above, bases upon the CArray class, in the same file you might do the following:

C++

/////////////////////////////////////////////////////////////////////////////
// CCuteBundle<TYPE, ARG_TYPE>

template<class TYPE, class ARG_TYPE = const TYPE>
class CCuteBundle : public CObject
{
public:
// Construction
	CCuteBundle();

// Attributes
	INT_PTR GetSize() const;
	INT_PTR GetCount() const;
         INT_PTR GetUpperBound() const;
	BOOL IsEmpty() const;

// Operations
         void SortMePlease(INT_PTR nIndex, ARG_TYPE sortElement);

         // Accessing elements
	TYPE& GetAt(INT_PTR nIndex);
	void SetAt(INT_PTR nIndex, ARG_TYPE newElement);
	TYPE& ElementAt(INT_PTR nIndex);

         // overloaded operator helpers
	const TYPE& operator[](INT_PTR nIndex) const;
	TYPE& operator[](INT_PTR nIndex);

 
// Implementation
protected:
	TYPE* m_pData;   // the actual array of data
	INT_PTR m_nSize;     // # of elements (upperBound - 1)

};

So OK so far. Then You need to Actually Implement the functions. The implementation exists with in the same header file:

C++

////////////////////////////////////////////////////////////////////////////////////////////////CCuteBundle<TYPE, ARG_TYPE> inline functions

template<class TYPE, class ARG_TYPE>
AFX_INLINE INT_PTR CCuteBundle<TYPE, ARG_TYPE>::GetSize() const
    { return m_nSize; }

template<class TYPE, class ARG_TYPE>
AFX_INLINE INT_PTR CCuteBundle<TYPE, ARG_TYPE>::GetCount() const
    { return m_nSize; }

template<class TYPE, class ARG_TYPE>
AFX_INLINE BOOL CCuteBundle<TYPE, ARG_TYPE>::IsEmpty() const
    { return m_nSize == 0; }

AFX_INLINE INT_PTR CCuteBundle<TYPE, ARG_TYPE>::GetUpperBound() const
	{ return m_nSize-1; }

template<class TYPE, class ARG_TYPE>
AFX_INLINE TYPE& CCuteBundle<TYPE, ARG_TYPE>::GetAt(INT_PTR nIndex)
{ 
	ASSERT(nIndex >= 0 && nIndex < m_nSize);
	if(nIndex >= 0 && nIndex < m_nSize)
		return m_pData[nIndex]; 
	AfxThrowInvalidArgException();		
}

template<class TYPE, class ARG_TYPE>
AFX_INLINE void CCuteBundle<TYPE, ARG_TYPE>::SetAt(INT_PTR nIndex, ARG_TYPE newElement)
{ 
	ASSERT(nIndex >= 0 && nIndex < m_nSize);
	if(nIndex >= 0 && nIndex < m_nSize)
		m_pData[nIndex] = newElement; 
	else
		AfxThrowInvalidArgException();		
}

template<class TYPE, class ARG_TYPE>
AFX_INLINE const TYPE& CCuteBundle<TYPE, ARG_TYPE>::operator[](INT_PTR nIndex) const
	{ return GetAt(nIndex); }

template<class TYPE, class ARG_TYPE>
AFX_INLINE TYPE& CCuteBundle<TYPE, ARG_TYPE>::operator[](INT_PTR nIndex)
	{ return ElementAt(nIndex); }

So now in the sections below, are using the functions just defined above, so ground work is key to your implementation.

C++

template<class TYPE, class ARG_TYPE>
void CCuteBundle<type,>::SortMePlease(INT_PTR nIndex, ARG_TYPE sortElement) 
{
         ASSERT_VALID(this);
         ASSERT(sortElement != NULL);
         ASSERT(nIndex > 0);
 
         if(m_pData[nIndex - 1] > sortElement)
         {
               m_pData[nIndex] = m_pData[nIndex - 1];
               //Do your decrementing or incrementing in your main program.
         }
         else
         {
               m_pData[nIndex] = sortElement;
         }
}

You may want to add some of the other CArray type functions just in case ...
Then use your new class in your Main Program.

Posted 2-Aug-13 21:59pm

The_Inventor

Updated 2-Aug-13 22:20pm

v3

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

mbue · Accepted Answer · 2013-08-06T08:08:00

Cannot see any problem for implementing a template sort function. The function you've declared is fully usable. But most sort functions need a compare function as parameter to compare different data types in the same function. Not always binary comparisation is required i.e. to compare records ore something else. To increase flexibility you should use a compare function.

(sorry if i'm going wrong to get the array of the vector class)
slightly modified your code and my additions:

C++

#pragma once
#include <iostream>
#include <vector>
#include <tchar.h>

using namespace std;

/** 
    Gets the position of the smallest element in a vector range.
    @param a the vector
    @param from the beginning of the range
    @param to the end of the range
    @return the position of the smallest element in 
    the range a[from]...a[to]
*/
int min_position(vector<int>& a, int from, int to)
{  
   int min_pos = from;
   int i;
   for (i = from + 1; i <= to; i++)
      if (a[i] < a[min_pos]) min_pos = i;
   return min_pos;
}
 
/** 
   Sorts a vector using the selection sort algorithm
   @param a the vector to sort
*/
 
void selection_sort(vector<int>& a)
{  
   unsigned int next; // The next position to be set to the minimum

   for (next = 0; next < a.size() - 1; next++)
   {  
      // Find the position of the minimum
      int min_pos = min_position(a, next, a.size() - 1);
      if (min_pos != next)
         swap(a[min_pos], a[next]);
   }
}


////////////////////////////////////////////////////
// substitutions
//#include "util.h"

#define  rand_seed()      srand(23)
#define  rand_int(L,H)    (L+rand()%(H-L))

void print(vector<int>& av)
{
   for (unsigned int i = 0; i < av.size(); i++)
      cout << av[i] << "\r\n";
}

////////////////////////////////////////////////////
// your template - only functioning for integer types
template <typename T>
void sort(T* A,int N)
{
  for(int n = 1;n < N;n++)
  {
    T        mover = A[n];
    int      k = n;
    while(k > 0)
    {
      if(A[k-1] > mover)
      {
        A[k] = A[k-1];
        k--;
      }
      else break;
    }
    A[k] = mover;
  }
}
////////////////////////////////////////////////////
// template with compare function - that works for all types
// the function has to be implemented!
template <typename T>
void sortwithfunction(T* A,const unsigned int N,int (*cmp)(T&,T&))
{
  for(unsigned int n = 1;n < N;n++)
  {
    T        mover = A[n];
    int      k = n;
    while(k > 0)
    {
      if( 0<cmp(A[k-1],mover) )
      {
        A[k] = A[k-1];
        k--;
      }
      else break;
    }
    A[k] = mover;
  }
}

////////////////////////////////////////////////////
int __cmpi(int& a,int& b){ return a-b; } // compare two integer values
////////////////////////////////////////////////////

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

  rand_seed();
  for (unsigned int i = 0; i < v.size(); i++)
  v[i] = rand_int(1, 100);

  cout << "--- before sort ------------------\r\n";
  print(v);

  switch(2) // test cases
  {
    case 0: selection_sort(v); break;
    case 1: sort(&v[0],v.size()); break;
    case 2: sortwithfunction(&v[0],v.size(),__cmpi); break;
  }

  cout << "--- after sort ------------------\r\n";
  print(v);

  _gettch();
  return 0;
}

Good luck.