TP3: Add merge sort implementation

[Algorithmic_C.git] / TP3 / tp3.c

diff --git a/TP3/tp3.c b/TP3/tp3.c
new file mode 100644 (file)
index 0000000..4caf275
--- /dev/null
+++ b/TP3/tp3.c
@@ -0,0 +1,62 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+void AfficheTab(int T[], int n) {
+    for (int i = 0; i < n; i++) {
+        printf("T[%d]=%d\n", i, T[i]);
+    }
+}
+
+void TriFusion(int T[], int n) {
+    int i = 0, j = 0, k = 0;
+    int* T1;
+    int* T2;
+
+    T1 = malloc(n/2*sizeof(int));
+    T2 = malloc((n - n/2)*sizeof(int));
+    
+    if (n > 1) {
+        for (int i = 0; i < n/2; 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]) {
+            T[i] = T1[k];
+            i++;
+            k++;
+        } else {
+            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);
+    } 
+}
+
+int main() {
+    int T[] = {4, 2, 7, 3, 8, 1, 6, 5};
+    int tabSize = sizeof(T)/sizeof(T[0]);
+    
+    AfficheTab(T, tabSize);
+
+    TriFusion(T,tabSize); 
+
+    AfficheTab(T, tabSize);
+
+    return 0;
+}