TP 2 exo3: randomly choose the pivot in quick sort

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

#include <stdio.h>
#include <stdlib.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) {
    // The optimal pivot choice is the median value in the tab
    int index_pivot = arc4random_uniform(n);
    int pivot = T[index_pivot];
    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;
}