Nuxt Dashboard Template

Voici une explication détaillée de l’algorithme de Tri à Bulles (ou Bubble Sort) que vous avez fourni.

1. Le principe général

Le tri à bulles fonctionne sur un principe très simple : il parcourt le tableau et compare les éléments deux par deux. Si deux éléments consécutifs sont dans le mauvais ordre (le précédent est plus grand que le suivant), il les échange.

Ce processus est répété jusqu’à ce que le tableau soit entièrement trié. On l’appelle “tri à bulles” car les plus grands éléments “remontent” petit à petit vers la fin du tableau, comme des bulles d’air remontant à la surface de l’eau.

2. Explication détaillée du code

Décortiquons votre algorithme ligne par ligne :

Les variables

n : La taille du tableau.
Tab : Le tableau à trier.
i et j : Les indices pour les boucles.
temp : Une variable temporaire indispensable pour effectuer l’échange de deux valeurs.

La boucle externe (`pour i de n jusqu'à 1 faire`)

C’est la boucle principale. Elle contrôle la partie du tableau qui reste à trier.

Au début, i vaut n (la fin du tableau).
À chaque tour de cette boucle, la plus grande valeur de la partie non triée est placée à la position i.
Une fois qu’une valeur est à sa place définitive (à la fin), on n’y touche plus. La boucle décrémente i (donc la zone de tri rétrécit par la droite).

La boucle interne (`pour j de 2 jusqu'à i faire`)

C’est ici que se fait le “travail sale”. Cette boucle parcourt le tableau de l’indice 2 jusqu’à l’indice i (la limite actuelle définie par la boucle externe).

Pour chaque j, on regarde le couple : l’élément actuel Tab[j] et son prédécesseur Tab[j-1].

La condition et l’échange (`si Tab[j-1] > Tab[j] alors ...`)

C’est le cœur de l’algorithme.

On regarde si l’élément de gauche (j-1) est plus grand que l’élément de droite (j).
Si c’est le cas, ils sont mal ordonnés.
On procède alors à la permutation (l’échange) grâce à la variable temp :
1. On sauvegarde Tab[j-1] dans temp.
2. On écrase Tab[j-1] avec Tab[j].
3. On met l’ancienne valeur sauvegardée dans Tab[j].

3. Exemple concret

Imaginons un tableau Tab = [5, 3, 8, 1] (donc n=4).

Premier passage (i = 4) : On va faire remonter le plus grand élément à la fin.

j=2 : Compare Tab[1] (5) et Tab[2] (3). 5 > 3, on échange. -> [3, 5, 8, 1]
j=3 : Compare Tab[2] (5) et Tab[3] (8). 5 < 8, rien à faire. -> [3, 5, 8, 1]
j=4 : Compare Tab[3] (8) et Tab[4] (1). 8 > 1, on échange. -> [3, 5, 1, 8]
Résultat : Le 8 (le plus grand) est bien à la fin (bulle remontée).

Deuxième passage (i = 3) : On travaille sur les 3 premiers éléments [3, 5, 1].

j=2 : Compare Tab[1] (3) et Tab[2] (5). 3 < 5, ok.
j=3 : Compare Tab[2] (5) et Tab[3] (1). 5 > 1, on échange. -> [3, 1, 5, 8]
Résultat : Le 5 est bien placé juste avant le 8.

Troisième passage (i = 2) : On travaille sur les 2 premiers éléments [3, 1].

j=2 : Compare Tab[1] (3) et Tab[2] (1). 3 > 1, on échange. -> [1, 3, 5, 8]
Résultat : Le tableau est trié.

4. Résumé visuel

Itération (i)	Action	État du tableau
Début	Tableau initial	`[5, 3, 8, 1]`
i = 4	Le 8 “remonte” à la fin	`[3, 5, 1, 8]`
i = 3	Le 5 “remonte” à sa place	`[3, 1, 5, 8]`
i = 2	Le 3 “remonte” à sa place	`[1, 3, 5, 8]`

5. Complexité

Complexité temporelle : La complexité est en O(n²). Cela signifie que si vous doublez la taille du tableau, le temps d’exécution est multiplié par 4. C’est un algorithme simple mais peu efficace pour les grandes quantités de données.
Complexité spatiale : En O(1). L’algorithme trie le tableau “sur place” (in-place), il ne nécessite pas de créer un nouveau tableau, seulement une petite variable temp.

Voici la méthode étape par étape pour déterminer soi-même ces complexités, en se basant sur le code fourni.

1. Calcul de la Complexité Temporelle (O(n²))

Pour calculer la complexité temporelle, il faut compter combien de fois les opérations principales sont exécutées en fonction de la taille du tableau (n).

L’opération principale ici est la comparaison (si Tab[j-1] > Tab[j]) et l’échange qui s’ensuit.

Étape A : Analyser les boucles

L’algorithme est constitué de deux boucles imbriquées (une boucle dans une autre).

La boucle externe (pour i de n jusqu'à 1) : Elle s’exécute n fois (de n jusqu’à 1).
La boucle interne (pour j de 2 jusqu'à i) : Le nombre de tours de cette boucle dépend de la valeur de i.
- Quand i = n (premier passage), la boucle interne fait environ n tours.
- Quand i = n-1 (deuxième passage), elle fait environ n-1 tours.
- …
- Quand i = 1 (dernier passage), elle fait 1 tour.

Étape B : Calculer le nombre total d’opérations

Pour trouver le coût total, il faut additionner le nombre de tours de la boucle interne pour chaque valeur de i. C’est la somme des entiers de 1 à n :

Total des itérations ≈ n + (n-1) + (n-2) + … + 1

C’est une suite arithmétique classique. La formule de la somme des n premiers entiers est :

Somme = (n × (n+1)) / 2 = (n^2 + n) / 2

Étape C : Simplifier avec la notation O

En complexité algorithmique, on utilise la notation “Grand O” qui ne garde que l’ordre de grandeur (ce qui pèse le plus lourd quand n est très grand).

On ignore les constantes (le / 2 disparaît).
On ignore les termes négligeables (le + n disparaît car n^2 est beaucoup plus grand que n).

Il nous reste donc : n^2. On écrit : O(n^2).

Note : C’est pour cela que si on double n (2n), le temps est multiplié par (2n)^2 = 4n^2, soit 4 fois plus long.

2. Calcul de la Complexité Spatiale (O(1))

Pour la complexité spatiale, on regarde la mémoire vive (RAM) nécessaire pour faire tourner l’algorithme. On ne compte pas l’entrée (le tableau Tab), mais seulement les variables supplémentaires créées par l’algorithme.

Étape A : Lister les variables supplémentaires

Regardons la section local de votre algorithme :

i : un entier.
j : un entier.
n : un entier.
temp : un entier.

Étape B : Évaluer l’impact de la taille n

Non. Qu’il y ait 10 ou 1 million d’éléments à trier, nous avons toujours besoin d’une seule case mémoire pour i, une pour j, une pour n et une pour temp.

Étape C : Conclusion

Comme la quantité de mémoire supplémentaire nécessaire est constante (elle ne dépend pas de n), on dit que la complexité est constante. On note cela : O(1).

On dit aussi que le tri est “en place” (in-place), car on réorganise le tableau directement sans en créer un nouveau (contrairement à d’autres algorithmes qui nécessiteraient un tableau de secours de taille n).

Voici les corrections et les solutions algorithmiques pour les travaux dirigés, en respectant la contrainte des points-virgules à chaque instruction.

Exercice 1

Énoncé : Développer une procédure qui permet de saisir 100 réels puis qui les affiche dans l’ordre inverse de leur saisie.

Solution : Pour inverser l’ordre d’affichage, il suffit de parcourir le tableau depuis le dernier élément (indice 100) jusqu’au premier (indice 1).

Procédure SaisirEtInverser();
Var T : tableau[1..100] de réel;
Var i : entier;
Début
    // Phase de saisie
    Pour i <- 1 à 100 faire
        Ecrire("Entrez le réel numéro ", i, " : ");
        Lire(T[i]);
    FinPour;

    // Phase d'affichage inverse
    Ecrire("Les nombres en ordre inverse sont :");
    Pour i <- 100 à 1 faire
        Ecrire(T[i]);
    FinPour;
Fin;

Exercice 2

Énoncé : Développer une procédure qui permet de saisir 100 réels puis qui les affiche dans l’ordre croissant (en implémentant le tri à bulle et le tri par sélection).

Comme l’exercice demande d’implémenter les deux techniques, voici deux versions de la procédure.

Version A : Tri à Bulle

Le principe est de parcourir le tableau et d’échanger les éléments adjacents s’ils sont dans le mauvais ordre, jusqu’à ce que le tableau soit trié.

Procédure TriBulleSaisie();
Var T : tableau[1..100] de réel;
Var i, j : entier;
Var temp : réel;
Début
    // 1. Saisie des données
    Pour i <- 1 à 100 faire
        Ecrire("Entrez le réel numéro ", i, " : ");
        Lire(T[i]);
    FinPour;

    // 2. Tri à bulle
    Pour i <- 1 à 99 faire
        Pour j <- 1 à (100 - i) faire
            Si T[j] > T[j+1] alors
                // Échange
                temp <- T[j];
                T[j] <- T[j+1];
                T[j+1] <- temp;
            FinSi;
        FinPour;
    FinPour;

    // 3. Affichage du résultat
    Ecrire("Les nombres triés (bulle) sont :");
    Pour i <- 1 à 100 faire
        Ecrire(T[i]);
    FinPour;
Fin;

Version B : Tri par Sélection

Le principe est de chercher le plus petit élément du tableau et de le placer au début, puis de répéter l’opération pour le reste du tableau.

Procédure TriSelectionSaisie();
Var T : tableau[1..100] de réel;
Var i, j, min_idx : entier;
Var temp : réel;
Début
    // 1. Saisie des données
    Pour i <- 1 à 100 faire
        Ecrire("Entrez le réel numéro ", i, " : ");
        Lire(T[i]);
    FinPour;

    // 2. Tri par sélection
    Pour i <- 1 à 99 faire
        min_idx <- i;
        Pour j <- (i + 1) à 100 faire
            Si T[j] < T[min_idx] alors
                min_idx <- j;
            FinSi;
        FinPour;

        // Échange si nécessaire
        Si min_idx <> i alors
            temp <- T[i];
            T[i] <- T[min_idx];
            T[min_idx] <- temp;
        FinSi;
    FinPour;

    // 3. Affichage du résultat
    Ecrire("Les nombres triés (sélection) sont :");
    Pour i <- 1 à 100 faire
        Ecrire(T[i]);
    FinPour;
Fin;