#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include "tri_rapide.h"


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

void sousTriRapide(long* A, size_t first, size_t size){
    if(first+1 < size){
        size_t middle = partition(A,first,size);
        sousTriRapide(A,first,middle);
        sousTriRapide(A,middle+1,size);
    }
}

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

void permuter(long* A,size_t i,size_t j) {
    long inter = A[i];
    A[i] = A[j];
    A[j] = inter;
}