#include <stdio.h>


//quicksort sorteert de array "data" met "lengte" aantal elementen
void quicksort(int data[],int lengte)
{
   int i;
   int *resultaat = new int[lengte];
   int kleiner=0,groter=lengte-1;
   
   //als er geen of 1 element is, dan moet er niet gesorteerd worden
   if(lengte>1){ 
     
     // partition 
     //neem als pivot het eerste element
     for(i=1;i<lengte;i++){ //ga al de andere elementen af
       if(data[i]<data[0]){ //kleiner als pivot, plaats vooraan in resultaat
         resultaat[kleiner]=data[i];
         kleiner++;
       }else{ //groter als pivot, plaats achteraan in resultaat
         resultaat[groter]=data[i];
         groter--;
       }
     }
     resultaat[kleiner]=data[0]; //zet het pivot juist  (in het midden)

     //recursion
     for(i=0;i<lengte;i++) data[i]=resultaat[i]; //kopieer resultaat naar data
     if(lengte>2){      //als er minder als 3 elementen zijn, dan zijn ze daarjuist gesorteerd
       quicksort(data,kleiner);                    //sorteer groep voor pivot
       quicksort(data+kleiner+1,lengte-kleiner-1); //sorteer groep na pivot
     }
   }

   delete []resultaat;
}

#define LENGTE 10
int main()
{
   int data[LENGTE]={ 5,3,6,8,9,10,2,1 , 5, 11 };
   int i=0;

   for ( i=0; i<LENGTE; ++i) printf("%d ",data[i]);
   printf("\n");

   quicksort(data, LENGTE );

   for ( i=0; i<LENGTE; ++i) printf("%d ",data[i]);
   printf("\n");

   return 0;
}