// *****************************************************************************
// *****************************************************************************
//                                                                             *
//         platform : Fedora 16 x86_64                                         *
//         compiler : gcc-c++-4.6.2-1.fc16.x86_64                              *
//                                                                             *
// test 1 : g++ main.cpp && ./a.out                                            *
// test 2 : g++ -O2 main.cpp && ./a.out                                        *
// test 3 : g++ -O3 main.cpp && ./a.out                                        *
//                                                                             *
// original data : {12, -1, 2} to be sorted into : {-1, 2, 12}                 *
//                                                                             *
// *****************************************************************************
// *****************************************************************************

#include <stdint.h> // for uint32_t
#include <cstddef>  // for std::size_t and std::ptrdiff_t
#include <iostream> // for standard output
#include <cstdlib>  // for EXIT_SUCCESS and EXIT_FAILURE

// *****************************************************************************
// swap values pointed by x and y                                              *
// *****************************************************************************

template<typename T>
void
swap(T *const x, T *const y)
{
  if (*x!=*y) {
    const T tmp = *y;
    *y = *x;
    *x = tmp;
  };
}

// ---------------------------------------------------------------------------
// specialisation for T = float
// ---------------------------------------------------------------------------

template<>
inline
void
swap<float>(float *const x, float *const y)
{
  swap<uint32_t>(reinterpret_cast<uint32_t *const>(x),reinterpret_cast<uint32_t * const>(y));
}

// *****************************************************************************
// quicksort (with pointers)                                                   *
// --------------------------------------------------------------------------- *
// data are sorted in the range [ptr_start ; ptr_end[                          *
// *****************************************************************************

template<typename T>
void
quicksort(T *const ptr_start, const T *const ptr_end)
{
  const std::ptrdiff_t n = ptr_end-ptr_start;
  if (n>=2) {
    if (n==2) {
      if (*ptr_start>*(ptr_start+1)) {
	swap<T>(ptr_start,ptr_start+1);
      };
    }
    else {
      swap<T>(ptr_start,ptr_start+(n>>1));
      // std::cout<<*ptr_start<<std::endl; /* (uncomment to see the influence on the result) */
      T *ptr_left = ptr_start, *ptr_right = ptr_start+(n-1);
      const T pivot = *ptr_left++;
      while (ptr_left<ptr_right) {
	while ((ptr_left<ptr_end)&&(*ptr_left<=pivot)) {
       	  ptr_left++;
      	};
       	while ((ptr_right>ptr_start)&&(*ptr_right>pivot)) {
	  ptr_right--;
      	};
	if (ptr_left<ptr_right) {
	  swap<T>(ptr_left++,ptr_right--);
      	}
      };
      if ((ptr_right==ptr_left)&&(*ptr_right>pivot)) {
       	ptr_right--;
      };
      swap<T>(ptr_start,ptr_right);
      quicksort<T>(ptr_start,ptr_right);
      quicksort<T>(++ptr_right,ptr_end);
    };
  };
}


// *****************************************************************************
// main routine                                                                *
// *****************************************************************************

int
main(void)
{
  typedef float T;
  const std::size_t N = 3;
  T tab[N] = {12, -1, 2};
  std::cout<<"\noriginal data ( {12, -1, 2} )\n\n";
  for (std::size_t i=0;i<N;i++) {
    std::cout<<"\tdata["<<i<<"] : "<<tab[i]<<std::endl;
  };
  std::cout<<std::endl;
  quicksort<T>(tab,tab+N);
  std::cout<<"sorted data ( shoud be {-1, 2, 12} )\n\n";
  for (std::size_t i=0;i<N;i++) {
    std::cout<<"\tdata["<<i<<"] : "<<tab[i]<<std::endl;
  };
  std::cout<<std::endl;
  return (EXIT_SUCCESS);
}