Refine .gitignore some more.

[Algorithmic_C.git] / TP3 / tp3.c

diff --git a/TP3/tp3.c b/TP3/tp3.c
index 9198ad1e15ba4e245b857e124f170b28e609ee4f..52c2a6e398be161c61c1f8af0837bd79bbff265a 100644 (file)
--- a/TP3/tp3.c
+++ b/TP3/tp3.c
@@ -7,55 +7,57 @@ void AfficheTab(int T[], int n) {
     }
 }
 
-/** This quick sort implementation only work with 2^n array size */
 void TriFusion(int T[], int n) {
     int i = 0, j = 0, k = 0;
+    int milieu = n/2;
     int* T1;
     int* T2;
-
-    T1 = malloc(n/2*sizeof(int));
-    T2 = malloc(n/2*sizeof(int));
     
     if (n > 1) {
-        for (int i = 0; i < n/2; i++) {
+        T1 = malloc(milieu*sizeof(int));
+        T2 = malloc(((n - milieu)*sizeof(int)));
+        for (int i = 0; i < milieu; i++) {
             T1[i] = T[i];
-            T2[i] = T[i + n/2];
         }
-    TriFusion(T1, n/2);
-    TriFusion(T2, n/2);
-    while (k < n/2 && j < n/2) {
-        if (T1[k] <= T2[j]) {
+       for (int i = milieu; i < n; i++) {
+            T2[i - milieu] = T[i];
+       }
+        TriFusion(T1, milieu);
+        TriFusion(T2, n - milieu);
+        while (k < milieu && j < (n - milieu)) {
+            if (T1[k] <= T2[j]) {
+                T[i] = T1[k];
+                i++;
+                k++;
+            } else {
+                T[i] = T2[j];
+                i++;
+                j++;
+            }
+        }
+        while (k < milieu) {
             T[i] = T1[k];
             i++;
             k++;
-        } else {
+        }
+        while (j < n - milieu) {
             T[i] = T2[j];
             i++;
             j++;
-        }
-    }
-    while (k < n/2) {
-        T[i] = T1[k];
-        i++;
-        k++;
-    }
-    while (j < n/2) {
-        T[i] = T2[j];
-        i++;
-        j++;
-    }
-    free(T1);
-    free(T2);
+        } 
+        free(T1);
+        free(T2);
     } 
 }
 
 int main() {
-    int T[] = {2, 7, 2, 3, 4, 1, 5, 5};
+    //int T[] = {2, 7, 2, 3, 4, 1, 5, 5};
+    int T[] = {6, 2, 3, 1, 9, 10, 15, 13, 12, 17};
     int tabSize = sizeof(T)/sizeof(T[0]);
     
     AfficheTab(T, tabSize);
 
-    TriFusion(T,tabSize); 
+    TriFusion(T, tabSize);
 
     AfficheTab(T, tabSize);