Лист за преговор: Introduction aux algorithmes de tri et leur complexité

📋 Plan du Cours

1. Tri par sélection & complexité
2. Tri par insertion & décalages
3. Algorithmes de tri & principes
4. Complexité quadratique & cas pire
5. Fonctionnement & schémas explicatifs
6. Implémentation & vérification
7. Comparaison & impact sur performances
8. Étude du pire cas & décalages

📖 1. Tri par sélection & complexité

🔑 Notions clés & Définitions

• Tri par sélection : Algorithme de tri qui consiste à parcourir le tableau pour trouver le minimum, puis à échanger cet élément avec celui en début de sous-tableau non trié. Répète jusqu'à ce que tout le tableau soit trié.
• Complexité en temps : Mesure du nombre d'opérations effectuées par un algorithme en fonction de la taille de l'entrée, souvent exprimée en notation Big O.
• Pire cas : Situation où l'algorithme nécessite le plus de ressources (comparaisons, décalages) pour trier le tableau.
• Décalage : Opération consistant à déplacer un élément pour faire de la place à un nouvel élément lors du tri par insertion.
• Complexité quadratique (O(n²)) : Classe de complexité où le temps d'exécution croît proportionnellement au carré de la taille du tableau.

📝 Points essentiels

• Principe du tri par sélection : Trouver le plus petit élément dans la partie non triée, l'échanger avec le premier élément non trié, puis répéter pour la sous-partie restante.
• Étapes du tri par sélection :
  1. Parcourir le tableau pour identifier le minimum.
  2. Échanger le minimum avec l'élément en début de sous-tableau.
  3. Répéter pour la sous-section suivante jusqu'à ce que le tableau soit trié.
• Complexité : En pire cas, le nombre de comparaisons est de l'ordre de n(n-1)/2, ce qui donne une complexité en O(n²).
• Impact de la taille du tableau : Doublement de la taille du tableau multiplie par quatre le temps d'exécution pour un algorithme quadratique.

💡 À retenir

Le tri par sélection est simple à comprendre et à implémenter, mais sa complexité en O(n²) le rend inefficace pour de très grands tableaux. Il est principalement utilisé à des fins pédagogiques ou pour de petits ensembles de données.

📖 2. Tri par insertion & décalages

🔑 Notions clés & Définitions

• Tri par insertion : Algorithme de tri qui construit le tableau trié en insérant un à un chaque élément à sa place dans la partie déjà triée.
• Décalage : Opération consistant à déplacer une ou plusieurs valeurs d'une position vers une autre pour faire de la place à un nouvel élément ou pour réorganiser le tableau.
• Complexité en temps (worst-case) : Mesure du nombre d'opérations nécessaires pour trier dans le cas le plus défavorable, généralement en fonction de la taille du tableau.
• Complexité en O(n²) : Notation indiquant que le temps d'exécution croît proportionnellement au carré de la taille du tableau, caractéristique des algorithmes quadratiques comme le tri par insertion dans le pire cas.
• Pire cas : Situation où le tableau est initialement trié à l’envers, nécessitant le maximum de décalages ou comparaisons.

📝 Points essentiels

• Principe du tri par insertion : Parcourir le tableau en insérant chaque nouvel élément à sa position correcte dans la partie déjà triée, en décalant les éléments plus grands vers la droite.
• Processus : À chaque étape, on compare l’élément courant avec ceux qui le précèdent, décalant ces derniers vers la droite jusqu’à trouver la position adéquate.
• Décalages : Lorsqu’un élément doit être inséré, tous les éléments plus grands doivent être décalés d’une position vers la droite pour faire place.
• Complexité : Dans le pire cas, le nombre de décalages est la somme 1 + 2 + ... + (n-1), soit en O(n²).
• Avantages : Simple à implémenter, efficace pour de petits tableaux ou tableaux presque triés.
• Inconvénients : Performant peu pour de grands tableaux non triés, en raison de sa complexité quadratique.

💡 À retenir

Le tri par insertion est un algorithme simple, dont la complexité en worst-case est en O(n²), ce qui le rend peu adapté aux très grands ensembles, mais idéal pour des petits tableaux ou des données presque triées. Son fonctionnement repose sur des décalages successifs pour insérer chaque élément à sa place.

📖 3. Algorithmes de tri & principes

🔑 Notions clés & Définitions

• Tri par sélection : Algorithme de tri qui consiste à sélectionner à chaque étape le plus petit élément du tableau non trié, puis à l’échanger avec l’élément en cours de traitement. Il répète cette opération jusqu’à ce que le tableau soit trié.
• Tri par insertion : Algorithme de tri qui construit le tableau trié en insérant un à un chaque élément dans sa position correcte, en décalant les éléments plus grands vers la droite.
• Complexité en temps : Mesure du nombre d’opérations nécessaires pour exécuter un algorithme, souvent exprimée en notation Big O.
• Complexité quadratique (O(n²)) : Classe de complexité où le temps d’exécution augmente proportionnellement au carré de la taille du tableau.
• Pire cas : Situation où l’algorithme doit effectuer le maximum d’opérations, par exemple, un tableau trié à l’envers pour le tri par insertion ou sélection.
• Décalage : Opération de décaler les éléments d’un tableau pour insérer un nouvel élément à sa position correcte dans le tri par insertion.

📝 Points essentiels

• Les algorithmes de tri par sélection et insertion ont une complexité en O(n²), ce qui les rend inefficaces pour de très grands tableaux.
• Le tri par sélection fonctionne en sélectionnant le minimum dans le tableau non trié et en l’échangeant avec l’élément en cours, répétant cette étape jusqu’à ce que le tableau soit trié.
• Le tri par insertion construit progressivement un tableau trié en insérant chaque nouvel élément à sa place, en décalant les éléments plus grands.
• La complexité dans le pire cas pour ces algorithmes est atteinte lorsque le tableau est dans l’ordre inverse.
• La différence principale réside dans la méthode de traitement : sélectionne le minimum à chaque étape (tri par sélection) ou insère chaque élément à sa position correcte (tri par insertion).
• La performance de ces algorithmes double ou quadruple selon la taille du tableau, en fonction de leur complexité quadratique.

💡 À retenir

Les algorithmes de tri par sélection et insertion sont simples à comprendre et à implémenter, mais leur efficacité diminue rapidement avec la taille des données, car ils ont une complexité en O(n²).

📖 4. Complexité quadratique & cas pire

🔑 Notions clés & Définitions

• Complexité en temps : Mesure du nombre d'opérations effectuées par un algorithme en fonction de la taille de l'entrée (notée n).
• Cas pire : Situation où l'algorithme nécessite le plus grand nombre d'opérations pour traiter un problème, souvent utilisé pour analyser la limite de performance.
• Complexité quadratique (O(n²)) : Classe de complexité où le nombre d'opérations croît proportionnellement au carré de la taille de l'entrée.
• Tri par sélection : Algorithme de tri qui, à chaque étape, sélectionne le plus petit élément du tableau non trié et l’échange avec le premier élément non trié.
• Tri par insertion : Algorithme de tri qui construit le tableau trié en insérant chaque nouvel élément à sa position correcte dans la partie déjà triée.

📝 Points essentiels

• La complexité du tri par sélection et du tri par insertion est en O(n²) dans le pire cas, ce qui signifie que le temps d'exécution augmente quadratiquement avec la taille du tableau.
• Le pire cas pour ces algorithmes survient lorsque le tableau est initialement trié à l'envers (décroissant), nécessitant le maximum de comparaisons et de décalages.
• La somme des comparaisons dans le tri par sélection pour un tableau de n éléments est donnée par la formule :
  $S = \frac{n(n-1)}{2}$ ce qui confirme la complexité en O(n²).
• La croissance du temps d'exécution est significative : en doublant la taille du tableau, le temps quadruple pour ces algorithmes quadratiques.
• La complexité en décalages pour le tri par insertion dans le pire cas est également en O(n²), avec une croissance similaire.

💡 À retenir

Les algorithmes de tri par sélection et par insertion ont une complexité quadratique en pire cas, ce qui limite leur efficacité pour de très grands tableaux, surtout lorsque ceux-ci sont initialement dans l’ordre inverse.

📖 5. Fonctionnement & schémas explicatifs

🔑 Notions clés & Définitions

• Algorithme de tri : Procédé permettant de réorganiser les éléments d’un tableau selon un ordre précis (croissant ou décroissant).
• Tri par sélection : Algorithme qui sélectionne à chaque étape le plus petit élément du sous-tableau non trié et l’échange avec le premier élément non trié.
• Tri par insertion : Algorithme qui construit le tableau trié en insérant un élément à la fois à sa place dans la partie déjà triée.
• Complexité en temps : Mesure du nombre d’opérations effectuées par un algorithme en fonction de la taille de l’entrée, souvent exprimée en notation Big O.
• Pire cas : Situation où l’algorithme nécessite le plus de ressources (ex. tableau trié à l’envers).
• Décalage : Opération consistant à déplacer un élément pour faire de la place à un autre lors du tri par insertion.

📝 Points essentiels

• Fonctionnement du tri par sélection :
  1. Parcourir le tableau de gauche à droite.
  2. À chaque étape, trouver le minimum dans la partie non triée.
  3. Échanger ce minimum avec l’élément en début de sous-tableau non trié.
  4. Répéter jusqu’à ce que tout le tableau soit trié.
• Fonctionnement du tri par insertion :
  1. Parcourir le tableau en partant du deuxième élément.
  2. Comparer l’élément courant avec ceux de la partie triée à gauche.
  3. Décaler les éléments plus grands vers la droite pour insérer l’élément à sa place.
  4. Continuer jusqu’à la fin du tableau.
• Complexité :
  • Les deux algorithmes ont une complexité en O(n²) dans le pire cas.
  • Le pire cas survient lorsque le tableau est trié à l’envers, nécessitant le maximum de décalages ou de comparaisons.
• Schémas explicatifs :
  • Illustrent étape par étape le processus de sélection ou d’insertion, en montrant l’évolution du tableau.

💡 À retenir

Les algorithmes de tri par sélection et par insertion sont simples à comprendre et à implémenter, mais leur complexité quadratique limite leur efficacité pour de très grands tableaux. Leur compréhension repose sur la visualisation étape par étape de leur fonctionnement à travers des schémas explicatifs.

📖 6. Implémentation & vérification

🔑 Notions clés & Définitions

• Algorithme : Suite finie d'instructions permettant de résoudre un problème ou d'effectuer une tâche spécifique.
• Complexité algorithmique : Mesure du nombre d'opérations ou du temps d'exécution en fonction de la taille des données d'entrée, souvent exprimée en notation Big O.
• Tri par sélection : Algorithme de tri qui sélectionne à chaque étape le plus petit élément du tableau non trié et l’échange avec l’élément en début de sous-tableau.
• Tri par insertion : Algorithme de tri qui construit le tableau trié en insérant un à un chaque élément à sa position correcte dans la partie déjà triée.
• Pire cas : Situation où l’algorithme nécessite le plus de ressources (comparaisons, décalages) pour exécuter le tri.
• Décalage : Opération consistant à déplacer un élément pour faire de la place à un autre lors du tri par insertion.

📝 Points essentiels

• Fonctionnement du tri par sélection : Parcourt le tableau, trouve le minimum dans la partie non triée, puis échange avec l’élément en début de cette partie. Répète jusqu’à ce que tout soit trié.
• Fonctionnement du tri par insertion : Parcourt le tableau, insère chaque nouvel élément à sa position correcte dans la partie déjà triée en décalant les éléments plus grands vers la droite.
• Complexité : Les deux algorithmes ont une complexité en temps en O(n²) dans le pire cas, ce qui peut devenir coûteux pour de grands tableaux.
• Vérification : Implémentation en code, test avec différents tableaux, et observation de l’évolution du tableau étape par étape.
• Impact de la taille : Doublement de la taille du tableau multiplie par 4 le temps d’exécution pour un algorithme quadratique.

💡 À retenir

Les algorithmes de tri par sélection et insertion sont simples à comprendre et à implémenter, mais leur complexité quadratique limite leur efficacité pour de très grands ensembles de données. Leur vérification pratique permet d’appréhender leur comportement en fonction de la taille et de la configuration initiale du tableau.

📖 7. Comparaison & impact sur performances

🔑 Notions clés & Définitions

• Complexité algorithmique : Mesure du nombre d'opérations ou du temps d'exécution d'un algorithme en fonction de la taille de l'entrée (notée n).
• Complexité en temps : Évalue la rapidité d'un algorithme, notamment dans le pire cas, en fonction de n.
• Complexité quadratique (O(n²)) : Situation où le temps d'exécution croît proportionnellement au carré de la taille du tableau. Typique des algorithmes de tri par sélection et insertion.
• Pire cas : Situation où l'algorithme doit effectuer le maximum d'opérations, par exemple, un tableau trié à l'envers pour le tri par insertion.
• Décalage : Opération de décalage des éléments dans un tableau lors du tri par insertion.
• Algorithme de tri par sélection : Tri consistant à sélectionner à chaque étape le plus petit élément et à le placer en début de tableau.
• Algorithme de tri par insertion : Tri consistant à construire progressivement un tableau trié en insérant chaque nouvel élément à sa position correcte.

📝 Points essentiels

• Tri par sélection :
  • Parcourt le tableau pour trouver le minimum, puis échange avec l'élément en cours.
  • Complexité en pire cas : O(n²), car chaque étape nécessite de comparer tous les éléments restants.
  • Avantage : simplicité, mais inefficace pour de grands tableaux.
• Tri par insertion :
  • Insère chaque nouvel élément dans la partie déjà triée en décalant les éléments plus grands.
  • Complexité en pire cas : O(n²), notamment lorsque le tableau est trié à l’envers.
  • Avantage : efficace pour tableaux presque triés.
• Impact sur la performance :
  • La complexité quadratique implique que doubler la taille du tableau quadruple le temps d’exécution.
  • Ces algorithmes sont peu performants pour de très grands ensembles de données.
• Choix de l’algorithme :
  • Préférer des algorithmes plus efficaces (ex. tri rapide, tri fusion) pour de gros tableaux.
  • Utiliser tri par insertion ou sélection pour des petits tableaux ou des cas pédagogiques.

💡 À retenir

Les algorithmes de tri par sélection et insertion ont une complexité en O(n²), ce qui limite leur efficacité pour de grands ensembles de données, mais ils restent fondamentaux pour comprendre les concepts de tri et d’analyse de performance algorithmique.

📖 8. Étude du pire cas & décalages

🔑 Notions clés & Définitions

• Pire cas : Situation où l'algorithme nécessite le plus grand nombre d'opérations, généralement lorsque le tableau est dans l'ordre inverse ou déjà trié à l'envers.
• Complexité en temps : Mesure du nombre d'opérations effectuées par un algorithme en fonction de la taille de l'entrée.
• Complexité quadratique (O(n²)) : Classe de complexité où le nombre d'opérations croît proportionnellement au carré de la taille du problème, typique des tris par sélection et insertion dans leur pire cas.
• Décalages : Opérations de déplacement d'éléments dans un tableau lors du tri par insertion, correspondant à la nécessité de faire de la place pour insérer un élément.
• Somme arithmétique : Calcul de la somme 1 + 2 + ... + (n-1), qui croît en O(n²), utilisée pour déterminer la complexité dans le pire cas.

📝 Points essentiels

• La complexité du tri par sélection et du tri par insertion dans le pire cas est en O(n²), en raison du nombre de comparaisons ou décalages nécessaires.
• Lors du tri dans l'ordre inverse, chaque élément doit être déplacé à sa position correcte, ce qui entraîne un nombre maximal de décalages ou comparaisons.
• La somme 1 + 2 + ... + (n-1) représente le nombre total de comparaisons ou décalages dans le pire cas, ce qui confirme la complexité quadratique.
• La croissance du temps d'exécution est significative : doubler la taille du tableau quadruple le temps pour ces algorithmes.
• La compréhension des décalages est essentielle pour analyser la performance dans le pire cas du tri par insertion.

💡 À retenir

L'étude du pire cas montre que les algorithmes de tri par sélection et insertion ont une complexité en O(n²), ce qui impacte leur efficacité sur de grands tableaux, notamment lorsque ceux-ci sont déjà dans l'ordre inverse.

📊 Tableaux de Synthèse

Critère	Tri par sélection	Tri par insertion
Principe	Sélectionne le minimum, échange avec début	Insère chaque élément à sa place, décalages
Complexité en moyenne/pire	O(n²)	O(n²)
Cas optimal	Déjà trié	Déjà trié
Cas pire	Tri inversé	Tri inversé
Opérations principales	Comparaisons, échanges	Comparaisons, décalages
Utilisation principale	Petits tableaux, pédagogie	Petils tableaux, presque triés

Critère	Tri par sélection	Tri par insertion
Méthode de traitement	Sélection du minimum à chaque étape	Insertion dans la partie triée
Nombre d’opérations dans le pire cas	$\frac{n(n-1)}{2}$ comparaisons	$\frac{n(n-1)}{2}$ décalages
Complexité	O(n²)	O(n²)
Adapté pour	Petits ensembles	Petits ou presque triés

⚠️ Pièges & Confusions Fréquentes

1. Confondre la méthode de sélection (minimum) avec l’insertion (place correcte).
2. Croire que le tri par insertion est efficace pour de grands tableaux — il est en O(n²).
3. Sous-estimer l’impact du pire cas, notamment lorsque le tableau est inversé.
4. Confondre le nombre d’échanges et de décalages dans le tri par insertion.
5. Ignorer que la complexité quadratique limite l’utilisation pour de gros ensembles.
6. Confondre la complexité moyenne et le pire cas, qui sont tous deux en O(n²).
7. Confondre la croissance du temps d’exécution avec la taille du tableau (doublement → quadruplement).

✅ Checklist Examen

1. Expliquer le principe du tri par sélection.
2. Décrire le fonctionnement du tri par insertion.
3. Comparer la complexité en temps des deux algorithmes.
4. Identifier le cas pire pour le tri par insertion.
5. Identifier le cas pire pour le tri par sélection.
6. Expliquer ce qu’est un décalage dans le contexte du tri par insertion.
7. Définir la complexité quadratique et donner un exemple.
8. Illustrer le fonctionnement d’un tri par sélection avec un schéma.
9. Illustrer le fonctionnement d’un tri par insertion avec un schéma.
10. Expliquer pourquoi ces algorithmes sont inefficaces pour de très grands tableaux.
11. Décrire la différence entre le traitement dans le tri par sélection et le tri par insertion.
12. Analyser la croissance du temps d’exécution quand la taille du tableau double.