Tp structure de données en langage c ensa fes 2020 2021 stru

Télécharger PDF

Les algorithmes de tri

Définition et types

Définition :

Répartir en plusieurs classes et selon certains critères, sans éliminer.
Un algorithme de tri est, en informatique ou en mathématiques, un algorithme qui permet d'organiser une collection d'objets selon une relation d'ordre déterminée. Les objets à trier sont des éléments d'un ensemble muni d'un ordre total.

Types de tri :

Le tri par sélection : (ou tri par extraction) est un algorithme de tri par comparaison. Cet algorithme est simple, mais considéré comme inefficace car il s'exécute en temps quadratique en fonction du nombre d'éléments à trier, et non en temps pseudolinéaire.
Le tri à bulles (ou tri par propagation) : est un algorithme de tri. Il consiste à comparer répétitivement les éléments consécutifs d'un tableau et à les permuter lorsqu'ils sont mal triés.
Le tri par insertion : C'est un algorithme de tri classique. La plupart des personnes l'utilisent naturellement pour trier des cartes à jouer.
Le tri par fusion : est un algorithme de tri par comparaison stable. L'opération principale de l'algorithme est la fusion, qui consiste à réunir deux listes triées en une seule.
...

Tri par insertion : Algorithme

procedure triInsertion(entier[] tab)
    entier i;
    entier tmp;
    entier k;
    pour (i de 2 à N en incrémentant de 1) faire
        tmp <- tab[i];
        k <- i;
        tant que (k > 1 et tab[k - 1] > tmp) faire
            tab[k] <- tab[k - 1];
            k <- k - 1;
        fin tant que
        tab[k] <- tmp;
    fin pour
fin procedure

Pour placer tab[i], on utilise une variable intermédiaire tmp pour conserver sa valeur que l'on compare successivement à chaque élément tab[i-1], tab[i-2], ... que l'on déplace vers la droite tant que sa valeur est supérieure à celle de tmp. On affecte alors à l’emplacement dans le tableau laissé libre par ce décalage la valeur de tmp.

Tri par insertion : Code

void Tri_Insertion(Liste *liste){
    Liste *Nliste=Allouer();
    Element* tmp;
    int max;
    while(liste->longueur >= 0){
        tmp=liste->Tete;
        max=tmp->valeur;
        while(tmp!=NULL){
            if(max < tmp->valeur) max=tmp->valeur;
            tmp=tmp->suivant;
        }
        AjouDebut(Nliste, max);
        AfficherL(Nliste);
        if(max==liste->Tete->valeur) SuppDebut(liste);
        else SuppVal(liste, max);
    }
}

Tri à bulles : Principe

Le tri à bulles consiste à parcourir le tableau, tant qu’il n’est pas trié, et à permuter les couples d’éléments consécutifs mal ordonnés. On sait que le tableau est trié si lors d’un parcours, aucun couple d’éléments n’a été permuté.

Tri à bulles : Algorithme

procedure triBulle(entier[] tab)
    entier i, k;
    entier tmp;
    pour (i de N à 2 en décrémentant de 1) faire
        pour (k de 1 à i-1 en incrémentant de 1) faire
            si (tab[k] > tab[k+1]) alors
                tmp <- tab[k];
                tab[k] <- tab[k+1];
                tab[k+1] <- tmp;
            fin si
        fin pour
    fin pour
fin procedure

Le « tri à bulles » consiste à parcourir le tableau tab en permutant toute paire d’éléments consécutifs (tab[k], tab[k+1]) non ordonnés, ce qui est un échange et nécessite donc une variable intermédiaire de type entier. Après le premier parcours, le plus grand élément se retrouve dans la dernière case du tableau, en tab[N], et il reste donc à appliquer la même procédure sur le tableau composé des éléments tab[1], ..., tab[N-1].

Tri à bulles : Code

void Tri_Bulles(Liste* liste){
    Element *tmp,*cmp;
    for(tmp=liste->Tete; tmp->suivant!=NULL; tmp=tmp->suivant){
        for(cmp=tmp; cmp!=NULL; cmp=cmp->suivant){
            if(tmp->valeur > cmp->valeur) Permuter(tmp,cmp);
        }
    }
    AfficherL(liste);
}

Tri par fusion : Principe

Le tri par fusion applique le principe « diviser pour régner ». En effet, étant données deux suites d’éléments triés, de longueurs respectives L1 et L2, il est très facile d’obtenir une troisième suite d’éléments triés de longueur L1 + L2, par « interclassement » (ou fusion) des deux précédentes suites. Il est à noter que la procédure de fusion nécessite un tableau intermédiaire aussi grand que le nombre d’éléments à interclasser.

Tri par fusion : Algorithme

procedure fusion(entier[] tab, entier[] tmp, entier debut, entier mil, entier fin)
    entier k;
    entier i <- debut;
    entier j <- mil + 1;
    pour (k de debut à fin en incrémentant de 1) faire
        si ((j > fin) ou (i <= mil et tab[i] < tab[j])) alors
            tmp[k] <- tab[i];
            i <- i + 1;
        sinon
            tmp[k] <- tab[j];
            j <- j + 1;
        fin si
    fin pour
    pour (k de debut à fin en incrémentant de 1) faire
        tab[k] <- tmp[k];
    fin pour
fin procedure

Tri par sélection : Algorithme (pour tableaux)

procedure triSelection(entier[] tab)
    entier i, k;
    entier minIndex;
    entier tmp;
    pour (i de 1 à N-1 en incrémentant de 1) faire
        /* recherche du numéro de l'élément minimum dans la sous-liste non triée */
        minIndex <- i;
        pour (k de i+1 à N en incrémentant de 1) faire
            si (tab[k] < tab[minIndex]) alors
                minIndex <- k;
            fin si
        fin pour
        /* Échange l'élément courant avec l'élément minimum trouvé */
        tmp <- tab[i];
        tab[i] <- tab[minIndex];
        tab[minIndex] <- tmp;
    fin pour
fin procedure

Cet algorithme consiste à trouver dans le tableau le numéro de l’élément le plus petit de la partie non triée, c’est-à-dire l’entier minIndex tel que tab[k] >= tab[minIndex] pour tout k. Une fois ce numéro trouvé, les éléments tab[i] et tab[minIndex] sont échangés – cet échange nécessite une variable temporaire de type entier – puis la même procédure est appliquée sur la suite d’éléments restante à trier.

Tri par sélection : Principe et implémentation par liste

Le tri par sélection consiste simplement à sélectionner l’élément le plus petit de la suite à trier, à l’enlever, et à répéter itérativement le processus tant qu’il reste des éléments dans la suite. Au fur et à mesure, les éléments enlevés sont stockés dans une pile.

Lorsque la suite à trier est stockée dans un tableau, on s'arrange pour représenter la pile dans le même tableau que la suite : la pile est représentée au début du tableau, et chaque fois qu’un élément est enlevé de la suite, il est remplacé par le premier élément qui apparaît à la suite de la pile, et prend sa place. Lorsque le processus s’arrête, la pile contient tous les éléments de la suite triés dans l’ordre croissant.

Tri par sélection : Code (pour liste chaînée avec pile)

void Tri_Selection(Liste* liste){
    Pile* pile=(Pile*)malloc(sizeof(Pile));
    pile->premier=NULL;
    Element*tmp=liste->Tete;
    int min;
    while(liste->longueur >= 0 ){
        tmp=liste->Tete;
        min=tmp->valeur;
        while(tmp!=NULL){
            if(min>tmp->valeur) min=tmp->valeur;
            tmp=tmp->suivant;
        }
        Empiler(pile, min);
        AfficherP(pile);
        if(min==liste->Tete->valeur) SuppDebut(liste);
        else SuppVal(liste,min);
    }
}

Foire Aux Questions (FAQ)

Qu'est-ce qu'un algorithme de tri ?

Un algorithme de tri est une méthode pour organiser une collection d'objets ou d'éléments (nombres, lettres, etc.) selon un ordre spécifique, comme croissant ou décroissant. Il permet de structurer les données pour faciliter leur recherche ou leur traitement ultérieur.

Pourquoi existe-t-il plusieurs types d'algorithmes de tri ?

Différents algorithmes de tri existent car ils n'ont pas tous les mêmes performances ou caractéristiques. Certains sont plus efficaces pour de petites collections de données, d'autres pour de grandes. Certains sont stables (maintenant l'ordre relatif des éléments égaux), d'autres non. Le choix dépend des besoins spécifiques de l'application, de la taille des données et des contraintes de temps et de mémoire.

Quel est l'algorithme de tri le plus efficace ?

Il n'y a pas un seul "meilleur" algorithme de tri en toutes circonstances. Des algorithmes comme le tri rapide (Quicksort) ou le tri fusion (Mergesort) sont généralement très efficaces pour de grandes quantités de données avec une complexité moyenne en O(n log n). Cependant, pour de très petites listes, des algorithmes plus simples comme le tri par insertion peuvent être plus rapides en raison de leurs faibles constantes. La performance dépend également de la nature des données initiales (déjà presque triées, aléatoires, inversées).