#include <iostream.h>

template < class T >
void swap(T& left, T& right)
{
   T temp;

   temp  = left;
   left  = right;
   right = temp;
}

template < class T >
int partition(T a[], int left, int right)
{
   T target = a[right];
   int  i   = left -1;
   int  j   = right;

   while (1)
   {                                       // *4*
         while ( i < j )
	 {
            i++;
            if (a[i] >= target) break;
         }

         while ( j > i )
	 {
            j--;
            if (a[j] <= target) break;
         }

         if (i >= j)
            break;

         swap( a[i], a[j]);
      }

      swap( a[i], a[right] );         // *2*

      return i;
}

template < class T >
void quicksort(T a[], int left, int right)
{
   cout << "..... Entering quicksort: " << left << ' ' << right << endl;

   if (left >= right)
      return;

   int split = partition(a, left, right);

   quicksort( a, left,    split-1);
   quicksort( a, split+1, right  );          // *3*

   cout << "........... Exiting quicksort : " << left
                                       << ' ' << right << endl;
}

void main()
{
   char buffer[100];
   cout << "Enter up to 100 chars: ";
   cin.getline(buffer, 100);

   cout << "Unsorted: " << buffer << endl;

   int length = strlen(buffer);
   quicksort(buffer, 0, length-1);              // *1*

   cout << "Sorted:   " << buffer << endl;
}