tridec.c

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

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

void triFusionDec(long* A, size_t size) {
  sousTriFusionDec(A, 0, size);
}

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

void copySousTableDec(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 fusionDec(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);

    copySousTableDec(A, ag, first, n1);
    copySousTableDec(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 triRapideDec(long* A, size_t n) {
    sousTriRapideDec(A,0,n);
}

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

size_t partitionDec(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){
            permuterDec(A,i,j);
            i++;
        }
    }
    permuterDec(A,i,size-1);
    return i;
}

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