TP2 exo3: Add quick sort implementation.

[Algorithmic_C.git] / TP2 / exo3 / exo3.c

diff --git a/TP2/exo3/exo3.c b/TP2/exo3/exo3.c
new file mode 100644 (file)
index 0000000..2970b00
--- /dev/null
+++ b/TP2/exo3/exo3.c
@@ -0,0 +1,58 @@
+#include <stdio.h>
+
+void permuter(int T[], int i1, int i2) {
+    int tmp = T[i1];
+    T[i1] = T[i2];
+    T[i2] = tmp;
+}
+
+void AfficheTab(int T[], int n) {
+    for (int i = 0; i < n; i++) {
+        printf("T[%d]=%d\n", i, T[i]);
+    }
+}
+
+void TriRapide(int T[], int n) {
+    int pivot = T[0];
+    int TP[n];
+    int TG[n];
+    int np = 0;
+    int ng = 0;
+
+    if (n == 1) {;}
+    else if (n == 2) {
+        if (T[0] > T[1]) { permuter(T, 0, 1); }
+    }
+    else if (n > 2) {
+        for (int i = 1; i < n; i++) {
+            if (T[i] < pivot) {
+                TP[np] = T[i];
+                np++;
+            } else { 
+                TG[ng] = T[i];
+                ng++;
+            }
+        }   
+        TriRapide(TP, np);
+        TriRapide(TG, ng);
+        for (int i = 0; i < np; i++) {
+            T[i] = TP[i];
+        }
+        T[np] = pivot;
+        for (int i = 0; i < ng; i++) {
+            T[np + 1 + i] = TG[i];
+        }
+    }
+}
+
+int main() {
+    int T[7] = {4, 2, 7, 3, 8, 6, 5};
+    
+    AfficheTab(T, 7);
+    
+    TriRapide(T, 7);
+
+    AfficheTab(T, 7);
+
+    return 0;
+}