README.md

Projet_Pne

METHODE DE QUICKSORT

FONCTION PARTITION

static void partition(list_t * L, elmlist_t * pivot, list_t * val_inf, list_t * val_sup, int (cmpFct)(void, void*)) { for (elmlist_t * cur = L->head; cur != NULL; cur = cur->suc) { //on parcourt la liste de la tête jusqu'à 0 if (cmpFct(get_data(cur), get_data(pivot)) < 0) //cmpfct va decider si le data est inferiur
queue(val_inf, get_data(cur));
else queue(val_sup, get_data(cur)); } }

FONCTION QUICKSORT

Etape (1)

void quick_sort(list_t * L, int (cmpFct)(void, void*)) { assert(L && cmpFct); //on verifier L et CmpFct

if (L->numelm > 1) { 
   
    elmlist_t * pivot = get_head(L); //la tete sera un pivot et on le retire de la liste
    L->head = get_suc(pivot); 
    pivot->pred = NULL;
    pivot->suc = NULL;
}

Etape (2)

//on créer deux nouveaux liste list_t * val_inf_pivot = new_list(); list_t * val_sup_pivot = new_list();

Etape (3)

//on appelle le fonction partition partition(L,pivot,val_inf_pivot,val_sup_pivot,cmpFct);

Etape (4)

if (is_empty(val_inf_pivot)) { //le liste sera le pivot s'il n'y en a pas L->head = pivot; L->tail = pivot; L->numelm = 1; } else { quick_sort(val_inf_pivot, cmpFct); L->head = val_inf_pivot->head; L->tail = val_inf_pivot->tail; L->numelm = val_inf_pivot->numelm; pivot->pred = L->tail; L->tail->suc = pivot; L->tail = pivot; L->numelm += 1; }

    if (!is_empty(val_sup_pivot)) {
        quick_sort(val_sup_pivot, cmpFct);
        val_sup_pivot->head->pred = pivot;
        pivot->suc = val_sup_pivot->head;
        L->tail = val_sup_pivot->tail;
        L->numelm += val_sup_pivot->numelm;
    }

Etape (5)

//on liberé leur pointeur respectif free(val_inf_pivot); free(val_sup_pivot); } }

#outils git remote add origin https://gitlab.univ-lorraine.fr/e87374u/projet_pne.git git branch -M main git push -uf origin main