Lbouvier master patch 19792

TP1/tris.c

+#include "tris.h"
+
+/**
+ * Algo de tri par insertion
+*/
+void triInsertion(long* A, size_t n) {
+  int cle,j;
+  for(int i=1; i < n; i++){
+    cle=A[i];
+    j=i-1;
+    while(j >= 0 && A[j] > cle){
+        A[j+1]=A[j];
+        j--;
+    }
+    A[j+1]=cle;
+  }
+}
+
+/**
+ * Algo de tri par fusion
+*/
+void triFusion(long* A, size_t n) {
+  sousTriFusion(A,0,n);
+}
+
+void sousTriFusion(long* A, size_t p, size_t r){ 
+    if(p<r-1){
+      size_t q=(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){
+    int n1 = (int)q - (int)p;
+    int n2 = (int)r - (int)q;
+
+    long* Ag = malloc(sizeof(long)*n1);
+    long* Ad = malloc(sizeof(long)*n2);
+
+    memcpy(Ag, &A[p], n1*sizeof(long));
+    memcpy(Ad, &A[q], n2*sizeof(long));
+
+    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++;
+    }
+    free(Ag);
+    free(Ad);
+}
+
+/**
+ * Algo de tri "rapide"
+*/
+void triRapide(long* A, size_t n) {
+  sousTriRapide(A, 0, n);
+}
+
+void sousTriRapide(long *A, size_t p, size_t r){ 
+  size_t max = -1;
+  if(r-1 != max && 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)
+{
+  long mem, pivot = A[r-1];
+  size_t i = p;
+  
+  for(size_t j = p; j <= r - 2; j++) {
+    if(A[j] <= pivot) {
+      mem = A[i];
+      A[i] = A[j];
+      A[j] = mem;
+      i++;
+    }
+  }
+
+  mem = A[i];
+  A[i] = A[r - 1];
+  A[r-1] = mem;
+
+  return i;
+}
\ No newline at end of file