//////////////////////////////////
// Rapid Sort & Function Templates
// By: *LuckY*
// lucky760@yahoo.com
//////////////////////////////////
// perhaps I over-commented

#include <iostream>
using namespace std;
#include <cstring> //for the strlen() function

/* function prototypes */

//function template (discussed later) to display
//the contents of any generic array by passing
//the address of the first element and the number
//of elements in the array. this is much better
//than using a bunch of 'for' loops with 'cout's
template <typename T>
void show(const T*,int);

//pass the array and the number of elements to the
//intermediary function. it will format the arguments
//properly and pass them to the actual sort procedure
template <typename T>
void r_sort(T*,int);

//the actual sort procedure. it takes the array, the 
//index of its first element, and the index of its last
//element
template <typename T>
void do_r_sort(T*,int,int);

int main() {
  //I'm hard-coding this array of char here, when in fact you 
  //can use any generic array (ie: int,short,long,float,double)
  //because the function template allows you to do so
  char chr[] = "The quick brown fox jumped over the lazy dogs.";  

  show(chr,strlen(chr)); //display the original array

  r_sort(chr,strlen(chr)); //do the sorting

  show(chr,strlen(chr)); //display the newly sorted array

  return 0;
}

template <typename T>
void r_sort(T *list,int count) {
  //pass the beginning values to the do_r_sort function
  //the first index is always 0 and the index of the last
  //index is 1 less than the element count, which is why
  //we have 'count-1'
  //if we didn't use this intermediary, we'd have to make 
  //ugly function calls to the do_q_sort function from the
  //main program. we don't want that.
  do_r_sort(list,0,count-1);
}

template <typename T>
void show(const T *arr,int num) {
  //from the first to the last elements of the given array
  //we do a cout. I commented out the " " because we
  //are dealing with a string, so we don't want spaces 
  //between each letter, but if it was a numeric array, we'd
  //want to leave it in.
  for (int i=0;i<num;++i) 
    cout << arr[i] /*<< " "*/;
  cout << endl;
}  

template <typename T>
void do_r_sort(T *arr,int basel,int baser) {
  //type T is the type which was passed to the function
  //so in the case of this example, type T is 'char'
  //if you passed an array of double, T would be 'double' etc...
  T temp;
  int biggest,smallest;
  
  /* find the biggest element */
  //this will start 'left' at the 'basel' index and 'right' at
  //the 'baser' value. if the value at index left is greater
  //than the one at right, we move index right to the left one
  //element and vice versa. we continue this until left and
  //right meet. In other words, we will keep moving the index
  //of the smaller value until both indexes meet. this will
  //assign the index to variable 'biggest'
  //(side note: there's no 3rd element in the 'for' loop 
  // because we do the update of left and right in the body)
  for (int left=basel,right=baser;left<right; )
    biggest = arr[left] >= arr[right] ? --right : ++left;

  /* place biggest at end of array */
  //here we copy the last value of the array to a temp variable
  //then we put the biggest value (of the entire array) into the
  //last (or rightmost) element because we are sorting for
  //left to right -- smallest to biggest
  //then we put the temp value into the slot where the 'biggest'
  //one just was. IOW, we swap the biggest value with the last
  //element's value
  temp = arr[baser];
  arr[baser] = arr[biggest];
  arr[biggest] = temp;

  /* find the smallest element */
  //same as above except for the smallest element
  for (int left=basel,right=baser;left<right; )
    smallest = arr[left] <= arr[right] ? --right : ++left;

  /* place smallest at head of array */
  temp = arr[basel];
  arr[basel] = arr[smallest];
  arr[smallest] = temp;

  //we move the baser value in one from the right and
  //the basel value in one from the left then we check to see
  //if there are still some elements in between the two indexes
  //that need to be sorted. if there are, the function calls 
  //itself passing only the new scope of the array because
  //we don't have to check the leftmost value and the rightmost
  //as we already know that they are not out of order.
  //this is recursion -- the function calling itself -- and it
  //will continue until there is nothing more to sort
  --baser;
  ++basel;
  if (basel < baser) 
    do_r_sort(arr,basel,baser);
}

/*A little bit about function templates:
  The syntax for a function template is this

    template <typename [name of generic type]>
    [return type] [function name] ([argument list]);

  This is used for the function prototype and the definition. The
  'name of generic type' as specified on the template line MUST be
  used in the argument list at least once.
  Then when you use the variables of the passed type in your function,
  you use the same typename that you specified. So, if we said:

    template <typename Blah> //etc..

  we would do a:

    Blah x;

  to declare a variable of the same type that was passed.
  The function template is actually just a blueprint for the compiler.
  No code is actually created from the code of the template. Once you
  pass something to the function, lets say a 'double' value, the
  compiler will read the blueprint and create an instantiation, or the
  actual 'double' code that will do the procedure of the template as
  specified.
*/