tris.c

#include <math.h>
#include <stdlib.h>
#include <stdio.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);
  printf("Tri fusion\n");
}

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);
    }
    printf("Sous Tri fusion\n");
}

void copySousTable(long* mainT, long* underT, size_t id, size_t size) {
  size_t i = 0;
  for(; id < size; ++id) {
    mainT[id] = underT[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);
    printf("Malloc\n");

    copySousTable(A, ag, first, n1);
    copySousTable(A, ad, middle, n2);
    printf("CopySousTable\n");

    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] = ag[indg];
        indd++;
      }
      ++i;
    }

    free(ag);
    free(ad);
}