#include "algos.h"
#include <string.h>

void triInsertion(long* A, size_t n){
    long cle = 0;
    size_t max = 0;
    max--;
    for(size_t i = 1; i<n; i++){
        cle=A[i];
        size_t j = i - 1;
        while (j != max && A[j] > cle ){
            A[j+1] = A[j];
            j = j-1;
        }
        A[j+1] = cle;
    }
}


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

void fusion(long * A, size_t p, size_t q, size_t r){
    size_t n1 = q-p;
    size_t n2 = r-q;

    long Ad[n2];
    memset(Ad, 0, n2);
    int j =0;
    for(size_t i = q; i<r; i++){
        Ad[j] = A[i];
        j++;
    }

    long Ag[n1];
    memset(Ag, 0, n1);
    j =0;
    for(size_t i = p; i<q; i++){
        Ag[j] = A[i];
        j++;
    }

    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++;
    }
}

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

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

size_t partition(long* A, size_t p, size_t r) {
    printf("r >>>>>>>>>> %d\n", r);
    size_t max = 0;
    max--;
    size_t pivot = 0;
    if(r-1 != max){
        pivot = A[r-1];
    } 
    
    size_t i = p;
    long temp;
    for (size_t j = p; j < r-2; j++) {
        if (A[j] <= pivot) {
            temp = A[i];
            A[i] = A[j];
            A[j] = temp;
            i++;
        }
    }
    temp = A[i];
    A[i] = A[r-1];
    A[r-1] = temp;
    return i;
}

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