/* Correction TP 01 - Exercice 1 - Quicksort en C */

#include <stdio.h>
#include <stdbool.h>
#include <assert.h>

int partitionne(int* tab, int n) {
    int pivot = tab[0];
    // on place le pivot en fin de tableau (échange)
    tab[0] = tab[n-1];
    tab[n-1] = pivot;
    // on positionne les éléments
    int isep = 0; // indice de séparation
    for (int i = 0; i < n - 1; i += 1){
        int elt = tab[i]; // élément à insérer
        if (elt < pivot) {
            tab[i] = tab[isep];
            tab[isep] = elt;
            isep += 1;
        } else {
            // rien à faire ...
        }
    }
    // on place le pivot à l'emplacement sep
    int tmp = tab[isep];
    tab[isep] = pivot;
    tab[n-1] = tmp;
    return isep;
}

void tri_rapide(int* tab, int n){
    // trie en place les n éléments de tab 
    if (n >= 2){ // s'il y a plus d'un élément à trier ...
        // on partitionne et récupère l'indice final du pivot
        int ipivot = partitionne(tab, n);
        // on trie récursivement
        tri_rapide(tab, ipivot);
        tri_rapide(&tab[ipivot+1], n-1-ipivot);
    }
}

/* pour les tests : égalité de deux tableaux ?*/
bool egaux(int t1[], int t2[], int n){
    for (int i = 0; i < n; i += 1){
        if (t1[i] != t2[i]) return false;
    }
    return true;
}

// NB tests : la mise en place de tests 
// ne doit pas modifier le code des fonctions testées
int main(){
    printf("Début tests\n");

    // message d'erreur bizarre ...
    /* // test 0 : tableau à 0 élément 
    int t0[0] = {};
    int tt0[0] = {};
    tri_rapide(t0, 0);
    assert(egaux(t0, tt0, 0)); */

    // test 1 : tableau à 1 élément
    int t1[1] = {-5};
    int tt1[1] = {-5};
    tri_rapide(t1, 1);
    assert(egaux(t1, tt1, 1));

    // test 2 : tableau trié par ordre croissant 
    int t2[5] = {-5,3,4,11,17};
    int tt2[5] = {-5,3,4,11,17};
    tri_rapide(t2, 5);
    assert(egaux(t2, tt2, 5));

    // test 3 : tableau trié par ordre décroissant 
    int t3[5] = {11,6,3,0,-1};
    int tt3[5] = {-1,0,3,6,11};
    tri_rapide(t3, 5);
    //affiche(t3,0,5);
    assert(egaux(t3, tt3, 5));

    // test 4 : tableau de taille 2
    int t4[2] = {11,6};
    int tt4[2] = {6,11};
    tri_rapide(t4, 2);
    assert(egaux(t4, tt4, 2));

    // test 5 : tableau de taille 2
    int t5[2] = {6,11};
    int tt5[2] = {6,11};
    tri_rapide(t5, 2);
    assert(egaux(t5, tt5, 2));

    // test 6 : tableau quelconque
    int t6[10] = {7,11,-1,3,8,4,6,0,4,3};
    int tt6[10] = {-1,0,3,3,4,4,6,7,8,11};
    tri_rapide(t6, 10);
    assert(egaux(t6, tt6, 10));

    // test 7 : tableau avec répétitions
    int t7[10] = {11,4,11,11,11,4,4,11,4};
    int tt7[10] = {4,4,4,4,11,11,11,11,11};
    tri_rapide(t7, 9);
    assert(egaux(t7, tt7, 9));

    printf("Fin tests\n");
    return 0;
}