Introduction

Les listes chaînées simples nécessitent des approches spécifiques pour le tri, car l'accès direct aux éléments n'est pas possible. Nous explorerons trois méthodes principales : le tri par sélection, le tri à bulles et le tri rapide récursif, ainsi que la fusion de deux listes ordonnées.

Tri par sélection

Le principe consiste à rechercher l'élément maximal (ou minimal) dans la portion non triée, puis à le placer en position finale par manipulation des pointeurs. Contrairement aux tableaux, nous ne permutons pas les valeurs mais réorganisons les liens.

La démarche utilise plusieurs pointeurs : fin marque la fin de la zone triée, courant parcourt la liste, prec précède courant, et maxi avec prec_max identifient le nœud de valeur maximale.

Les trois opérations de rechaînage pour déplacer le maximum trouvé :

prec_max->suivant = maxi->suivant;  // Isoler le nœud
maxi->suivant = fin->suivant;       // Insérer après fin
fin->suivant = maxi;                // Finaliser l'insertion

void tri_selection(noeud *tete)
{
    noeud *fin, *prec, *courant, *maxi, *prec_max;
    
    for(fin = tete; fin && fin->suivant; fin = fin->suivant)
    {
        maxi = fin->suivant;
        prec_max = fin;
        
        for(courant = fin->suivant, prec = fin; courant; prec = courant, courant = courant->suivant)
        {
            if(courant->valeur > maxi->valeur) {
                maxi = courant;
                prec_max = prec;
            }
        }
        
        if(fin->suivant != maxi) {
            prec_max->suivant = maxi->suivant;
            maxi->suivant = fin->suivant;
            fin->suivant = maxi;
        }
    }
}

Tri à bulles

Cette méthode fait remonter les éléments légers vers la tête en comparant les paires adjacentes. Un pointeur limite marque la frontière entre les zones triée et non triée.

Illustration avec la séquence [5, 2, 4] :

Les opérations de rechaînage pour permuter deux nœuds adjacents :

prec->suivant = suivant_courant;           // 1
courant->suivant = suivant_courant->suivant; // 2
prec->suivant->suivant = courant;            // 3

void tri_bulles(noeud *tete)
{
    noeud *limite = NULL;
    noeud *prec, *courant;
    
    while(tete->suivant->suivant != limite)
    {
        prec = tete;
        courant = tete->suivant;
        
        while(courant->suivant != limite)
        {
            if(courant->valeur > courant->suivant->valeur)
            {
                prec->suivant = courant->suivant;
                courant->suivant = courant->suivant->suivant;
                prec->suivant->suivant = courant;
                courant = prec->suivant;
            }
            courant = courant->suivant;
            prec = prec->suivant;
        }
        limite = courant;
    }
}

Tri rapide récursif

L'algorithme divise la liste autour d'un pivot, place les éléments inférieurs à gauche et supérieurs à droite, puis traite récursivement chaque partition.

La fonction de partition utilise une technique d'insertion en tête pour les éléments inférieurs au pivot :

noeud* partitionner(noeud *tete, noeud *fin)
{
    noeud *pivot = tete->suivant;
    noeud *prec = pivot, *courant = pivot->suivant;
    
    while(courant && courant != fin)
    {
        if(courant->valeur < pivot->valeur) {
            prec->suivant = courant->suivant;
            courant->suivant = tete->suivant;
            tete->suivant = courant;
            courant = prec->suivant;
        } else {
            prec = prec->suivant;
            courant = courant->suivant;
        }
    }
    return pivot;
}

void tri_rapide(noeud *tete, noeud *fin)
{
    if(!tete || tete->suivant == fin || tete->suivant->suivant == fin)
        return;
    
    noeud *pivot = partitionner(tete, fin);
    tri_rapide(tete, pivot);
    tri_rapide(pivot, fin);
}

Fusion et tri de deux listes

Problème : concaténer deux listes puis les ordonner. Approche : chaînage direct suivi d'un tri à bulles.

void concatener(liste *premiere, liste *seconde)
{
    noeud *parcours = premiere;
    while(parcours->suivant)
        parcours = parcours->suivant;
    
    noeud *temp = seconde;
    seconde = seconde->suivant;
    free(temp);
    
    parcours->suivant = seconde;
}

Implémentation complète :

#include <stdio.h>
#include <stdlib.h>

typedef struct element {
    int valeur;
    struct element *suivant;
} noeud;

typedef struct {
    noeud *debut;
} liste_chainee;

void creer(liste_chainee *lst);
void afficher(const liste_chainee *lst);
void concatener(liste_chainee *a, liste_chainee *b);
void tri_bulles(liste_chainee *lst);

int main()
{
    liste_chainee a = {NULL}, b = {NULL};
    a.debut = malloc(sizeof(noeud));
    a.debut->suivant = NULL;
    b.debut = malloc(sizeof(noeud));
    b.debut->suivant = NULL;
    
    printf("Liste A (Ctrl+D pour terminer):\n");
    creer(&a);
    printf("Liste B:\n");
    creer(&b);
    
    concatener(&a, &b);
    tri_bulles(&a);
    printf("Résultat fusionné et trié:\n");
    afficher(&a);
    
    return 0;
}

void creer(liste_chainee *lst)
{
    int val;
    noeud *queue = lst->debut;
    
    while(scanf("%d", &val) != EOF) {
        noeud *nouveau = malloc(sizeof(noeud));
        nouveau->valeur = val;
        nouveau->suivant = NULL;
        queue->suivant = nouveau;
        queue = nouveau;
    }
}

void afficher(const liste_chainee *lst)
{
    for(noeud *p = lst->debut->suivant; p; p = p->suivant)
        printf("%d ", p->valeur);
    printf("\n");
}

void tri_bulles(liste_chainee *lst)
{
    noeud *limite = NULL;
    
    while(lst->debut->suivant->suivant != limite) {
        noeud *prec = lst->debut;
        noeud *courant = lst->debut->suivant;
        
        while(courant->suivant != limite) {
            if(courant->valeur > courant->suivant->valeur) {
                prec->suivant = courant->suivant;
                courant->suivant = courant->suivant->suivant;
                prec->suivant->suivant = courant;
                courant = prec->suivant;
            }
            courant = courant->suivant;
            prec = prec->suivant;
        }
        limite = courant;
    }
}