Using templates for insertion sort

[Karkalash]

Hello:

How can I improve on my function template to also do insertion sort on strings? I'm afraid I'm very new to templates, any hints appreciated.

Template looks like so:

template <class T>
void insSort(T arr[], int size)
{

	T key = arr[0];
	int j = 0;
	for(int i = 1; i < size; ++i)
	{
		key = arr[i];
		j = i - 1;
		while((j >= 0) && (arr[j] > key))
		{
			arr[j + 1] = arr[j];
			j -= 1;
		}
	arr[j + 1] = key;
	}
	
}

I have an array of names like so:

Name nameArray[] = { Name ( "Bob", "Davidson" ), 
                       Name ( "Harley", "Davidson" ),
                       Name ( "Kobe", "Bryant" ),
                       Name ( "Arnold", "Schwarzenegger" ),
                       Name ( "Keyser", "Soze" ),
                       Name ( "Irwin", "Fletcher" ),
                       Name ( "Sean", "Connery" ),
                       Name ( "George", "Lazenby" ),
                       Name ( "Roger", "Moore" ),
                       Name ( "Timothy", "Dalton" ),
                       Name ( "Pierce", "Brosnan" ) };

The name class looks like this:

#include <string>

using namespace std;

class Name {

public:
  string first;
  string last;

public:
  Name ( string f, string l ) {
    first = f; last = l;
  };

};

[mike_2000_17]

If you are going to create a function template to sort an array, I would recommend that you follow the same signature as the std::sort function. The problem with your function template is that it is not generic enough, it only applies to a C-style array of types which can be compare with > (greater-than) operator. If you look at std::sort, it doesn't suffer any of these problems, it applies to any container or array type and it allows a special comparison function to be provided.

template <typename BidirIterator, typename CompareFunction>
void insSort(BidirIterator first, BidirIterator last, CompareFunction compare)
{
        BidirIterator i = first; ++i;
	for(; i != last ; ++i)
	{
		typename std::iterator_traits<BidirIterator>::value_type key = *i;  // in C++11: auto key = std::move(*i);
		BidirIterator j = i;
                BidirIterator j_prior = j; --j_prior;
                while((j != first) && (compare(key, *j_prior)))
		{
			*j = *j_prior; // in C++11:  *j = std::move(*j_prior);
			--j; --j_prior;
		}
	        *j = key;  // in C++11: *j = std::move(key);
	}
};

template <typename BidirIterator>
void insSort(BidirIterator first, BidirIterator last) {
  insSort(first,last,std::less< typename std::iterator_type<BidirIterator>::value_type >());
};

So, for your problem, you should either create a < less-than operator overload for your Name class, or provide another comparison function to the insSort call.

As for calling insSort with an array, like you have, you just do:

insSort( &nameArray[0], &nameArray[0] + sizeof(nameArray) / sizeof(nameArray[0]) );

[Karkalash]

thanks for the tip, I'll do some operator overloads to get it working ^_^