#include "tris.h"

void fusion(long* A,size_t p,size_t q,size_t r){
	size_t n1 = q-p;
	size_t n2 = r-q;
	long* Ag = malloc(n1*sizeof(long));
	long* Ad = malloc(n2*sizeof(long));
	copierTableau(Ag,A+p,n1);
	copierTableau(Ad,A+q,n2);
	size_t indG = 0;
	size_t indD = 0;
	size_t i = p;
	while(i < r){
		if(indG == n1){
			A[i] = Ad[indD];
			indD++;
		}else if(indD == n2){
			A[i] = Ag[indG];
			indG++;
		}else if(Ag[indG] < Ad[indD]){
			A[i] = Ag[indG];
			indG++;
		}else{
			A[i] = Ad[indD];
			indD++;
		}
		i++;
	}
	free(Ad);
	free(Ag);
}

void sousTriFusion(long* A,size_t p,size_t r){
	if(p+1 < r){
		size_t q = (p+r)/2;
		sousTriFusion(A,p,q);
		sousTriFusion(A,q,r);
		fusion(A,p,q,r);
	}
}

void triFusion(long* A,size_t n){
	sousTriFusion(A,0,n);
}

void triInsertion(long* A, size_t n){
  for(size_t i = 1; i < n; i ++){
    long cle = A[i];
    size_t j = i - 1;
    while(j + 1 > j && A[j] > cle){ // ici on veut regarder tant que j >= 0
      A[j + 1] = A[j];
      j = j - 1;
    }
    A[j + 1] = cle;
  }
}

size_t partition(long* A,size_t p,size_t r){
	long pivot = A[r-1];
	size_t i = p;
	for(size_t j = p;j < r-1;j++){
		if(A[j] <= pivot){
			permuter(A+i,A+j);
			i++;
		}
	}
	permuter(A+i,A+r-1);
	return i;
}

void sousTriRapide(long* A,size_t p,size_t r){
	if(p+1 < r){
		size_t q = partition(A,p,r);
		sousTriRapide(A,p,q);
		sousTriRapide(A,q+1,r);
	}
}

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