# 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