#include <iostream>
#include <sstream>
#include <iomanip>
#include <cassert>
#include <string>
#include <functional>

using namespace std;

class test
{
public:
	test( string s = "", int i = 0 ) : ss(s), n(i)
	{
	}
	void set( string s = "", int i = 0 )
	{
		ss = s;
		n = i;
	}
	// comparators	
	static bool cmpInt(const test &left,const test &right)
	{return(left.n<right.n);}
	static bool cmpStr(const test &left,const test &right)
	{return(left.ss<right.ss);}
private:
	string ss;
	int n;

	friend ostream &operator<<(ostream &out,const test &t);
};

ostream &operator<<(ostream &out,const test &t)
{	out << "String part: " << t.ss << " Int part: " << t.n << endl;
}

   // EXCHANGES TWO INTEGER VALUES
   template <class eltType> void exchange(eltType &x,eltType &y)          
   // Arguments:
   // Both: INOUT: 
   {	eltType temp;
		temp=y; y=x; x=temp;
   }

// SORTS AN ARRAY (ASCENDING ORDER) USING SELECTION SORT ALGORITHM
template <class eltType> 
 void selSort(eltType *list,int items,bool (*le) (const eltType &,const eltType &))
// Arguments:
// list: INOUT - array to be sorted; 
// items IN: number of items to be sorted (items >= 0)
{
   int idxMax;  // subscript of each smallest item located by find_index_of_min
   for (int spot = items-1; spot > 0; spot--)
   {
      // Invariant: The elements in list[spot+1] through list[items-1] are in their
      //    proper place and spot > 0.

      // Find index of largest unsorted element 
      idxMax = spot;
      for (int idx = 0 ; idx < spot ; idx++)
		if (le(list[idxMax],list[idx]))
			idxMax = idx;
      // Exchange items at position idxMax and spot if different
      if (spot != idxMax)
		exchange (list[idxMax], list[spot]);
   }  // end for
}  // end sel_sort

int main()
{	test v[10];
	for ( int i = 0; i < 10; i++ )
	{	ostringstream os;
		os << (57-i);
		v[i].set( os.str(), i);
	}

	cout << "Sort by int part:\n";
	selSort( v, 10,test::cmpInt);
	for (int k=0;k<10;k++)
		cout <<  k << ": " << v[k];

	cout << "Sort by string part:\n";
	selSort( v, 10,test::cmpStr);
	for (int k=0;k<10;k++)
		cout <<  k << ": " << v[k];
	return(0);
}