Tri simple (échange, sélection) | Exercices corrigés

Concepts & Exercices

\(\text{Trier}(T) \rightarrow T_{\text{trié}}\)

Opération de tri d'un tableau

Tri sélection

O(n²)

Choisir le minimum

Tri bulles

O(n²)

Échanger adjacent

Comparaison

n(n-1)/2

Itérations

🎯

Définition : Le tri est une opération qui ordonne les éléments selon un critère.

📏

Types : Tri par sélection, tri à bulles, tri par insertion.

📋

Complexité : O(n²) pour les tris simples, O(n log n) pour les tris avancés.

⚡

Objectif : Ordonner les éléments pour faciliter les recherches ultérieures.

💡

Conseil : Utilisez le tri par sélection pour les petits tableaux

🔍

Attention : Les tris simples ont une complexité quadratique

⚡

Astuce : Le tri à bulles peut détecter si le tableau est déjà trié

📋

Méthode : Étudiez les itérations et les échanges pour comprendre

Exercice 1

Tri par sélection d'un tableau d'entiers

Exercice 2

Tri à bulles avec détection d'optimisation

Exercice 3

Comparaison des algorithmes de tri simples

Exercice 4

Analyse de la complexité des tris simples

Exercice 5

Application des tris à des données réelles

Corrigé : Exercices 1 à 3

1 Tri par sélection

Définition :

Tri par sélection : Algorithme qui sélectionne le plus petit élément et le place au début.

Principe : Diviser le tableau en deux parties : triée et non triée.

Méthode du tri par sélection :

Rechercher le plus petit élément dans la partie non triée
Échanger cet élément avec le premier élément non trié
Déplacer la frontière entre les parties triée et non triée
Répéter jusqu'à ce que tout le tableau soit trié

Avant

T = [64, 34, 25, 12, 22]

Tri

Sélection

Après

T = [12, 22, 25, 34, 64]

Étape 1 : Initialisation

Tableau T = [64, 34, 25, 12, 22] - Taille n = 5

Partie triée : [], Partie non triée : [64, 34, 25, 12, 22]

Étape 2 : Première itération (i=0)

Chercher le minimum entre T[0] et T[4] : c'est T[3]=12

Échanger T[0] et T[3] → [12, 34, 25, 64, 22]

Partie triée : [12], Partie non triée : [34, 25, 64, 22]

Étape 3 : Deuxième itération (i=1)

Chercher le minimum entre T[1] et T[4] : c'est T[4]=22

Échanger T[1] et T[4] → [12, 22, 25, 64, 34]

Partie triée : [12, 22], Partie non triée : [25, 64, 34]

Étape 4 : Troisième itération (i=2)

Chercher le minimum entre T[2] et T[4] : c'est T[2]=25 (déjà bon)

Aucun échange nécessaire → [12, 22, 25, 64, 34]

Partie triée : [12, 22, 25], Partie non triée : [64, 34]

Étape 5 : Quatrième itération (i=3)

Chercher le minimum entre T[3] et T[4] : c'est T[4]=34

Échanger T[3] et T[4] → [12, 22, 25, 34, 64]

Partie triée : [12, 22, 25, 34, 64], Partie non triée : []

Itération	État du tableau	Élément trié	Comparaisons
0	[64, 34, 25, 12, 22]	-	4
1	[12, 34, 25, 64, 22]	12	4
2	[12, 22, 25, 64, 34]	22	3
3	[12, 22, 25, 64, 34]	25	2
4	[12, 22, 25, 34, 64]	34	1
Fini	[12, 22, 25, 34, 64]	64	0

                // Pseudo-code
                pour i de 0 à n-2:
                  min_index = i
                  pour j de i+1 à n-1:
                    si T[j] < T[min_index]:
                      min_index = j
                  échanger T[i] et T[min_index]
              

T_trié = [12, 22, 25, 34, 64]

Réponse finale :

Le tableau trié par sélection est [12, 22, 25, 34, 64].

Règles appliquées :

• Tri par sélection : Trouver le minimum et l'échanger avec la position actuelle

• Complexité : O(n²) car pour chaque élément, on cherche le minimum dans le reste

• Nombre d'échanges : Maximum n-1 échanges (optimal pour le nombre de mouvements)

2 Tri à bulles

Définition :

Tri à bulles : Algorithme qui compare les éléments adjacents et les échange si nécessaire.

Principe : Faire "remonter" les éléments plus grands vers la fin du tableau.

Avant

T = [5, 2, 8, 1, 9]

Tri

Bulles

Après

T = [1, 2, 5, 8, 9]

Étape 1 : Initialisation

Tableau T = [5, 2, 8, 1, 9] - Taille n = 5

Le tri à bulles compare les paires adjacentes et échange si nécessaire

Étape 2 : Première passe

Comparer T[0] et T[1]: 5 > 2 → échanger → [2, 5, 8, 1, 9]

Comparer T[1] et T[2]: 5 < 8 → pas d'échange → [2, 5, 8, 1, 9]

Comparer T[2] et T[3]: 8 > 1 → échanger → [2, 5, 1, 8, 9]

Comparer T[3] et T[4]: 8 < 9 → pas d'échange → [2, 5, 1, 8, 9]

Étape 3 : Deuxième passe

Comparer T[0] et T[1]: 2 < 5 → pas d'échange → [2, 5, 1, 8, 9]

Comparer T[1] et T[2]: 5 > 1 → échanger → [2, 1, 5, 8, 9]

Comparer T[2] et T[3]: 5 < 8 → pas d'échange → [2, 1, 5, 8, 9]

Comparer T[3] et T[4]: 8 < 9 → pas d'échange → [2, 1, 5, 8, 9]

Étape 4 : Troisième passe

Comparer T[0] et T[1]: 2 > 1 → échanger → [1, 2, 5, 8, 9]

Comparer T[1] et T[2]: 2 < 5 → pas d'échange → [1, 2, 5, 8, 9]

Comparer T[2] et T[3]: 5 < 8 → pas d'échange → [1, 2, 5, 8, 9]

Comparer T[3] et T[4]: 8 < 9 → pas d'échange → [1, 2, 5, 8, 9]

Étape 5 : Quatrième passe

Comparer T[0] et T[1]: 1 < 2 → pas d'échange

Comparer T[1] et T[2]: 2 < 5 → pas d'échange

Comparer T[2] et T[3]: 5 < 8 → pas d'échange

Comparer T[3] et T[4]: 8 < 9 → pas d'échange

Aucun échange effectué → le tableau est trié

Passe	État du tableau	Échanges	Trié ?
0	[5, 2, 8, 1, 9]	0	false
1	[2, 5, 1, 8, 9]	2	false
2	[2, 1, 5, 8, 9]	1	false
3	[1, 2, 5, 8, 9]	1	false
4	[1, 2, 5, 8, 9]	0	true

                // Pseudo-code
                pour i de 0 à n-2:
                  echangé = false
                  pour j de 0 à n-2-i:
                    si T[j] > T[j+1]:
                      échanger T[j] et T[j+1]
                      echangé = true
                  si non echangé:
                    arrêter
              

T_trié = [1, 2, 5, 8, 9]

Réponse finale :

Le tableau trié par bulles est [1, 2, 5, 8, 9].

Règles appliquées :

• Tri à bulles : Comparer les éléments adjacents et échanger si nécessaire

• Optimisation : Arrêter si aucune paire n'a été échangée

• Complexité : O(n²) dans le pire cas, mais O(n) dans le meilleur cas

3 Comparaison des tris

Définition :

Comparaison d'algorithmes : Analyse des performances selon différents critères.

Métriques : Complexité temporelle, complexité spatiale, nombre d'échanges.

Algo

Sélection vs Bulles

Comp

O(n²)

Échanges

Étape 1 : Analyse de la complexité

Tri par sélection : O(n²) comparaisons fixes (n(n-1)/2)

Tri à bulles : O(n²) comparaisons dans le pire cas, O(n) dans le meilleur

Étape 2 : Comparaison du nombre d'échanges

Tri par sélection : Maximum n-1 échanges (optimal)

Tri à bulles : Jusqu'à n(n-1)/2 échanges (pire cas)

Étape 3 : Stabilité

Tri par sélection : Instable (peut changer l'ordre des éléments égaux)

Tri à bulles : Stable (préserve l'ordre des éléments égaux)

Étape 4 : Performance pratique

Tri par sélection : Moins d'échanges → plus rapide pour les coûts d'échange élevés

Tri à bulles : Peut détecter le tri → plus rapide pour les tableaux presque triés

Caractéristique	Tri sélection	Tri bulles
Complexité	O(n²)	O(n²)
Échanges max	n-1	n(n-1)/2
Stabilité	Instable	Stable
Optimisation	Non	Oui
Meilleur cas	O(n²)	O(n)

Tri sélection = Moins échanges | Tri bulles = Plus stable

Réponse finale :

Le tri par sélection effectue moins d'échanges mais le tri à bulles est plus adaptable.

Règles appliquées :

• Comparaison : Analyser selon plusieurs critères (temps, espace, stabilité)

• Choix : Dépend du contexte d'utilisation et des contraintes

• Optimisation : Adapter l'algorithme au type de données traitées

Corrigé : Exercices 4 à 5

4 Analyse de complexité

Définition :

Complexité algorithmique : Mesure de la performance en fonction de la taille des données.

Notation O : Bornes supérieures asymptotiques des ressources nécessaires.

Algo

Tri sélection

Comp

O(n²)

Formule

n(n-1)/2

Étape 1 : Analyse du tri par sélection

Boucle extérieure : i de 0 à n-2 → (n-1) itérations

Pour chaque i, boucle intérieure : j de i+1 à n-1 → (n-1-i) itérations

Étape 2 : Calcul du nombre total de comparaisons

Σ(i=0 à n-2) (n-1-i) = Σ(k=1 à n-1) k = (n-1)n/2

Soit environ n²/2 comparaisons

Étape 3 : Analyse du tri à bulles

Boucle extérieure : i de 0 à n-2 → (n-1) itérations

Boucle intérieure : j de 0 à n-2-i → (n-1-i) itérations

Nombre total de comparaisons = (n-1)n/2 (même formule)

Étape 4 : Analyse du cas moyen et pire cas

Tri par sélection : Toujours O(n²) comparaisons, indépendamment de l'entrée

Tri à bulles : O(n²) pire cas, O(n) meilleur cas (tableau déjà trié)

Scénario	Tri sélection	Tri bulles
Meilleur cas	O(n²)	O(n)
Cas moyen	O(n²)	O(n²)
Pire cas	O(n²)	O(n²)
Échanges	O(n)	O(n²)

\(\text{Comparaisons} = \frac{n(n-1)}{2}\)

Nombre de comparaisons pour n éléments

Complexité = O(n²) pour les deux algorithmes

Réponse finale :

Les deux algorithmes ont une complexité quadratique dans le pire cas.

Règles appliquées :

• Complexité : Analyser le nombre d'opérations en fonction de la taille

• Comparaison : Considérer le meilleur, le moyen et le pire cas

• Évaluation : La complexité théorique guide le choix pratique

5 Application à des données réelles

Définition :

Application concrète : Utilisation des algorithmes sur des données du monde réel.

Contexte : Classement de scores, tri de notes, organisation de données.

Données

Notes = [15, 12, 8, 19, 11, 14]

Tri

Sélection

Résultat

[8, 11, 12, 14, 15, 19]

Étape 1 : Analyse des données

Tableau de notes : [15, 12, 8, 19, 11, 14] - 6 éléments

Objectif : Trier par ordre croissant pour classer les élèves

Étape 2 : Application du tri par sélection

Itération 1 : Chercher min dans [15, 12, 8, 19, 11, 14] → 8 → [8, 12, 15, 19, 11, 14]

Itération 2 : Chercher min dans [12, 15, 19, 11, 14] → 11 → [8, 11, 15, 19, 12, 14]

Itération 3 : Chercher min dans [15, 19, 12, 14] → 12 → [8, 11, 12, 19, 15, 14]

Itération 4 : Chercher min dans [19, 15, 14] → 14 → [8, 11, 12, 14, 15, 19]

Itération 5 : Chercher min dans [19, 15] → 15 → [8, 11, 12, 14, 15, 19]

Étape 3 : Interprétation des résultats

Classement final : [8, 11, 12, 14, 15, 19]

Meilleur score : 19, Pire score : 8, Médiane : (12+14)/2 = 13

Étape 4 : Analyse des performances

Pour 6 éléments : 6(6-1)/2 = 15 comparaisons

4 échanges effectués (moins que le maximum possible de 5)

Position	Note initiale	Note triée	Classement
0	15	8	6ème
1	12	11	5ème
2	8	12	4ème
3	19	14	3ème
4	11	15	2ème
5	14	19	1er

                // Application en Python
                def tri_selection(tableau):
                  n = len(tableau)
                  for i in range(n-1):
                    min_idx = i
                    for j in range(i+1, n):
                      if tableau[j] < tableau[min_idx]:
                        min_idx = j
                    tableau[i], tableau[min_idx] = tableau[min_idx], tableau[i]
                  return tableau
                
                notes = [15, 12, 8, 19, 11, 14]
                notes_triees = tri_selection(notes.copy())
                print(f"Notes triées: {notes_triees}")
                # Affiche: [8, 11, 12, 14, 15, 19]
              

Notes triées = [8, 11, 12, 14, 15, 19]

Réponse finale :

Le classement trié des notes est [8, 11, 12, 14, 15, 19].

Règles appliquées :

• Application : Les algorithmes de tri sont utiles pour classer des données

• Performance : Pour de petits jeux de données, les tris simples sont suffisants

• Interprétation : Les résultats triés facilitent l'analyse des données

Cours bien détaillé

\(\text{Tri}(T, n) = O(n^2)\)

Complexité des tris simples

🎯

Définition : Le tri est une opération qui ordonne les éléments selon un critère.

📏

Types : Tri par sélection, tri à bulles, tri par insertion.

📋

Complexité : O(n²) pour les tris simples, O(n log n) pour les tris avancés.

⚡

Objectif : Ordonner les éléments pour faciliter les recherches ultérieures.

💡

Conseil : Utilisez le tri par sélection pour les petits tableaux

🔍

Attention : Les tris simples ont une complexité quadratique

⚡

Astuce : Le tri à bulles peut détecter si le tableau est déjà trié

📋

Méthode : Étudiez les itérations et les échanges pour comprendre

✅

Vérification : Testez avec des cas limites (vide, trié, inversé)

🔄

Amélioration : Pour de grandes données, utilisez des tris avancés

Algorithmes de tri simples :

Tri par sélection : Choisir le minimum et l'échanger avec la position actuelle
Tri à bulles : Comparer les éléments adjacents et échanger si nécessaire
Tri par insertion : Insérer chaque élément à sa place dans la partie triée
Optimisation : Détecter si le tableau est déjà trié pour arrêter plus tôt

Règles importantes :

Les tris simples ont une complexité O(n²) dans le pire des cas
Le tri par sélection effectue moins d'échanges que le tri à bulles
Le tri à bulles peut détecter le tri précoce et s'arrêter plus tôt
La stabilité est importante pour préserver l'ordre des éléments égaux

Tri sélection

O(n²)

Moins d'échanges

Tri bulles

O(n²)

Peut s'arrêter tôt

Stabilité

Oui/non

Préserver l'ordre

\(\text{Comparaisons} = \frac{n(n-1)}{2}\)

Nombre de comparaisons dans le pire cas

Points clés à retenir :

• Les tris simples sont faciles à comprendre et à implémenter
• Ils ont une complexité quadratique, ce qui limite leur utilité pour les grandes données
• Le choix entre les algorithmes dépend du contexte d'utilisation
• La complexité théorique est un guide important pour le choix pratique
• La compréhension des algorithmes simples est fondamentale pour aborder les algorithmes avancés

Tri simple (échange, sélection)Exercices corrigés

Tri simple (échange, sélection)
Exercices corrigés