tris.c

#include <math.h>
#include "tris.h"

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

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

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

void copySousTable(long* mainT, long* underT, size_t id, size_t size) {
  for(size_t i = id; i < id+size; ++i) {
    underT[i-id] = mainT[i];
  }
}

void fusion(long* A, size_t first, size_t middle, size_t size) {
    size_t n1 = middle - first; // Nb elem dans A[p , q]  q exclu
    size_t n2 = size - middle;  // Nb elem dans A[q , r]  r exclu

    size_t indg = 0;
    size_t indd = 0;

    long* ag = malloc(sizeof(long) * n1);
    long* ad = malloc(sizeof(long) * n2);

    copySousTable(A, ag, first, n1);
    copySousTable(A, ad, middle, n2);

    int i = first;

    while(i < size) {
      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(ag);
    free(ad);
}

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

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

    long permuter = A[i];
    A[i] = A[r - 1];
    A[r - 1] = permuter;
    //permuter(A,i,size-1);
    
    return i;
}

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

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