//fcn.h
#include <cstdlib>
#include <iostream>

void quickSort(int*& a, int start, int end);
int partition(int*& a, int start, int end);
void sort(int*& a, int e1, int e2);

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

//fcn.cpp
#include <cstdlib>
#include <iostream>
#include "fcn.h"

using namespace std;

void swap(int*& a, int e1, int e2){
     int temp = a[e1];
     a[e1] = a[e2];
     a[e2] = temp;
}

int partition(int*& a, int start, int end){
     int pivot = a[start];
     int s1 = start;
     int fu = start + 1;
     end++;
     while(fu != end){
          if(a[fu] < pivot){
               swap(a, fu, s1 + 1);
               s1++;
          }
          fu++;
     }
     swap(a, s1, start);
     return s1;
}

void quickSort(int*& a, int start, int end){
     if(start < end){
          int middle = partition(a, start, end);
          quickSort(a, start, middle - 1);
          quickSort(a, middle + 1, end);
     }
}

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

//main.cpp  for testing

#include <cstdlib>
#include <iostream>
#include "fcn.h"

using namespace std;

int main(int argc, char *argv[])
{
     int* a = new int[6];
     a[0] = 9;
     a[1] = 1;
     a[2] = 3;
     a[3] = 6;
     a[4] = 5;
     a[5] = 4;

     quickSort(a,0,5);

     for(int i = 0; i < 6; i++){
          cout << a[i] << endl;
     }

     system("PAUSE");
     return EXIT_SUCCESS;
}

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

//how algorithm works (click the picture for larger image)