#include <iostream.h>
#include <stdlib.h>

// ------------------------------------------------------------------

class Integer
{
private:
   int data;
public:
   Integer ( int a ) { data=a; };
   Integer () {};
   int operator < ( Integer &b );
   int operator > ( Integer &b );
   int operator == ( Integer &b );
   Integer& operator = ( Integer &b );
   Integer& operator = ( int b );
   void Swap ( Integer &b );
   friend ostream& operator << ( ostream& o, Integer i );
};

int Integer::operator < ( Integer &b )
{
   return (data < b.data);
}

int Integer::operator > ( Integer &b )
{
   return (data > b.data);
}

int Integer::operator == ( Integer &b )
{
   return (data == b.data);
}

Integer& Integer::operator = ( Integer &b )
{
   data = b.data;
   return *this;
}

Integer& Integer::operator = ( int b )
{
   data = b;
   return *this;
}

void Integer::Swap ( Integer &b )
{
   int t = b.data;
   b.data = data;
   data = t;
}

ostream& operator << ( ostream& o, Integer i )
{
   o << i.data;
   return o;
}

// ------------------------------------------------------------------

class IntegerArray
{
public:
   Integer *data;
   int length;
//   IntegerArray ();
//   IntegerArray ( IntegerArray& i );
   ~IntegerArray ();
   void Initialize ( int len, int Upper = 10000 );
   void Initialize ( IntegerArray& i );
   void Randomize ( int Upper = 10000 );
   char *Sorted ();
   Integer & operator [] ( int index );
};

IntegerArray::IntegerArray ()
{
   length = 1;
   data = new Integer[length];
}

//IntegerArray::IntegerArray ( IntegerArray& i )
//{
//   length = i.length;
//   data = new Integer[length];
//   for ( int j=0; j<length; j++ )
//      data[j] = i.data[j];
//}

IntegerArray::~IntegerArray ()
{
   delete data;
}

void IntegerArray::Initialize ( int len, int Upper )
{
   delete data;
   length = len;
   data = new Integer[length];
   Randomize (Upper);
}

void IntegerArray::Initialize ( IntegerArray& i )
{
   delete data;
   length = i.length;
   data = new Integer[length];
   for ( int j=0; j<length; j++ )
      data[j] = i.data[j];
}

void IntegerArray::Randomize ( int Upper )
{
   for ( int i=0; i<length; i++ )
      data[i] = rand () % Upper;
}

char *IntegerArray::Sorted ()
{
   for ( int i=1; i<length; i++ )
      if (data[i-1] > data[i])
         return "unsorted";
   return "  sorted";
}

Integer& IntegerArray::operator [] ( int index )
{
   return data[index];
}

ostream& operator << ( ostream& o, IntegerArray &i )
{
   for ( int j=0; j<i.length; j++ )
   {
      o << (i.data)[j];
      o << " ";
   }
   return o;
}

// ------------------------------------------------------------------

class Sorter
{
public:
   long comps, swaps;
   Sorter ();
   void Reset ();
   int Less ( Integer &a, Integer &b );
   int Greater ( Integer &a, Integer &b );
   void Swap ( Integer &a, Integer &b );
   virtual void Sort ( IntegerArray &data ) = 0;
   friend ostream& operator << ( ostream& o, Sorter& s );
};

Sorter::Sorter ()
{
   Reset ();
}

void Sorter::Reset ()
{
   comps = 0;
   swaps = 0;
}

int Sorter::Less ( Integer &a, Integer &b )
{
   comps++;
   return (a < b);
}

int Sorter::Greater ( Integer &a, Integer &b )
{
   comps++;
   return (a > b);
}

void Sorter::Swap ( Integer &a, Integer &b )
{
   swaps++;
   a.Swap (b);
}

ostream& operator << ( ostream& o, Sorter& s )
{
   o << "Comparisons : " << s.comps << "  Swaps : " << s.swaps;
   return o;
}

// ------------------------------------------------------------------

class InsertSort : public Sorter
{
public:
   void Sort ( IntegerArray& data );
};

void InsertSort::Sort ( IntegerArray& data )
{
   for ( int i=1; i<data.length; i++ )
      for ( int j=i; (j>0) && Less (data[j], data[j-1]); j-- )
         Swap (data[j], data[j-1]);
}

// ------------------------------------------------------------------

class BubbleSort : public Sorter
{
public:
   void Sort ( IntegerArray& data );
};

void BubbleSort::Sort ( IntegerArray& data )
{
   for ( int i=0; i<data.length-1; i++ )
      for ( int j=data.length-1; j>i; j-- )
         if (Less (data[j], data[j-1]))
            Swap (data[j], data[j-1]);
}

// ------------------------------------------------------------------

class SelectionSort : public Sorter
{
public:
   void Sort ( IntegerArray& data );
};

void SelectionSort::Sort ( IntegerArray& data )
{
   for ( int i=0; i<data.length-1; i++ )
   {
      int lowindex = i;
      for ( int j=data.length-1; j>i; j-- )
         if (Less (data[j], data[lowindex]))
            lowindex = j;
      Swap (data[i], data[lowindex]);
   }
}

// ------------------------------------------------------------------

class ShellSort : public Sorter
{
public:
   void Sort ( IntegerArray& data );
   void InsertSort ( IntegerArray& data, int start, int n, int incr );
};

void ShellSort::Sort ( IntegerArray& data )
{
   for ( int i=data.length/2; i>2; i/=2 )
      for ( int j=0; j<i; j++ )
         InsertSort (data, j, data.length-j, i);
   InsertSort (data, 0, data.length, 1);
}

void ShellSort::InsertSort ( IntegerArray& data, int start, int n, int incr )
{
   for ( int i=incr; i<n; i+=incr )
      for ( int j=i; (j>=incr) && (Less (data[start+j], data[start+j-incr]));
            j-=incr )
         Swap (data[start+j], data[start+j-incr]);
}

// ------------------------------------------------------------------

class QuickSort : public Sorter
{
public:
   void Sort ( IntegerArray& data );
   void QSort ( IntegerArray& data, int i, int j );
   int Partition ( IntegerArray& data, int l, int r, Integer& Pivot );
};

void QuickSort::Sort ( IntegerArray& data )
{
   QSort (data, 0, data.length-1);
}

void QuickSort::QSort ( IntegerArray& data, int i, int j )
{
   int pivotindex = (i+j)/2;
   Swap (data[pivotindex], data[j]);
   int k = Partition (data, i-1, j, data[j]);
   Swap (data[k], data[j]);
   if ((k-i) > 1) QSort (data, i, k-1);
   if ((j-k) > 1) QSort (data, k+1, j);
}

int QuickSort::Partition ( IntegerArray& data, int l, int r, Integer& Pivot )
{
   do {
      while (Less (data[++l], Pivot));
      while (r && Greater (data[--r], Pivot));
      Swap (data[l], data[r]);
   } while (l < r );
   Swap (data[l], data[r]);
   return l;
}

// ------------------------------------------------------------------

class MergeSort : public Sorter
{
public:
   void Sort ( IntegerArray& data );
   void MSort ( IntegerArray& data, IntegerArray& temp, int left, int right );
};

void MergeSort::Sort ( IntegerArray& data )
{
   IntegerArray temp;
   temp.Initialize (data);
   MSort (data, temp, 0, data.length-1);
}

void MergeSort::MSort ( IntegerArray& data, IntegerArray& temp, int left, int right )
{
   int mid = (left+right)/2;
   if (left==right) return;
   MSort (data, temp, left, mid);
   MSort (data, temp, mid+1, right);
   for ( int i=left; i<=right; i++ )
      temp[i] = data[i];
   int i1=left, i2=mid+1;
   for ( int curr=left; curr<=right; curr++ )
   {
      if (i1 == mid+1)
         data[curr] = temp[i2++];
      else if (i2 > right)
         data[curr] = temp[i1++];
      else if (Less (temp[i1], temp[i2]))
         data[curr] = temp[i1++];
      else
         data[curr] = temp[i2++];
   }
}

// ------------------------------------------------------------------
// ------------------------------------------------------------------
// ------------------------------------------------------------------

class TestSuite
{
private:
   int i;
   IntegerArray iamaster[10], ia[10];
public:
   TestSuite ();
   void Test ( Sorter &s );
};

TestSuite::TestSuite ()
{
   for ( int i=0; i<10; i++ )
      iamaster[i].Initialize (100*(i+1), 500);
}

void TestSuite::Test ( Sorter &s )
{
   for ( int i=0; i<10; i++ )
   {
      s.Reset ();
      ia[i].Initialize (iamaster[i]);
      s.Sort (ia[i]);
      cout << "n=";
      cout.width (4);
      cout << ia[i].length << " | " << ia[i].Sorted () << "  | comps="; 
      cout.width (7);
      cout << s.comps << ", swaps=";
      cout.width (7);
      cout << s.swaps << "\n";
   }
}

int main ()
{
   TestSuite ts;

   InsertSort s1;
   cout << "\nInsertSort\n----------\n";
   ts.Test (s1);

   BubbleSort s2;
   cout << "\nBubbleSort\n----------\n";
   ts.Test (s2);

   SelectionSort s3;
   cout << "\nSelectionSort\n-------------\n";
   ts.Test (s3);

   ShellSort s4;
   cout << "\nShellSort\n---------\n";
   ts.Test (s4);

   QuickSort s5;
   cout << "\nQuickSort\n---------\n";
   ts.Test (s5);

   MergeSort s6;
   cout << "\nMergeSort\n---------\n";
   ts.Test (s6);

   return 0;
}