#include <stdio.h>
#include <stdlib.h>

#include "utils.h"

size_t partition(long* A,size_t p,size_t r,struct compte* c){
	long pivot = A[r-1];
	size_t i = p;
	for(size_t j = p;j < r-1;j++){
		if(comparer(A[j],"<=",pivot,c)/*A[j] <= pivot*/){
			permuter(A+i,A+j);
			c->ecrit += 3;
			i++;
		}
	}
	permuter(A+i,A+r-1);
	c->ecrit += 3;
	return i;
}

void sousTriRapide(long* A,size_t p,size_t r,struct compte* c){
	if(/*comparer(p+1,"<",r,c)*/p+1 < r){
		size_t q = partition(A,p,r,c);
		sousTriRapide(A,p,q,c);
		sousTriRapide(A,q+1,r,c);
	}
}

void triRapide(long* A,size_t n,struct compte* c){
	sousTriRapide(A,0,n,c);
}

int main(int argc,char** argv){
	long* A = malloc((argc-1)*sizeof(long));
	for(size_t i = 0;i < argc-1;i++){
		A[i] = atol(argv[i+1]);
	}
	struct compte c;
	initCompte(&c);
	printf("Tableau d'entrée: ");
	printTab(A,argc-1);
	triRapide(A,argc-1,&c);
	printf("Tableau de sortie: ");
	printTab(A,argc-1);
	printf("Comparaisons: %lu\nEcritures: %lu\n",c.comp,c.ecrit);
	free(A);
}