IS 122 - Structures de Données et Algorithmes : Cours 5

Cette série de fiches contient les concepts clés du cours 5 sur les algorithmes de tri (Insertion, Fusion, Rapide), la récursion par rapport à l'itération, et la stratégie 'Diviser pour régner'.

Tri par insertion (Insertion Sort)

Un algorithme de tri simple basé sur la comparaison qui construit le tableau trié final un élément à la fois, similaire à la façon dont on trie des cartes à jouer.

Complexité temporelle du tri par insertion (Pire cas)

La complexité est de $O(n^2)$, ce qui survient lorsque le tableau est initialement trié dans l'ordre inverse.

Complexité spatiale du tri par insertion

La complexité est de $O(1)$, car il s'agit d'un algorithme de tri en place qui ne nécessite pas de mémoire supplémentaire.

Itération

La répétition d'un ensemble d'instructions à l'aide de boucles comme "for" ou "while", se terminant lorsqu'une condition devient fausse.

Récursion

Une fonction qui s'appelle elle-même, nécessitant impérativement un cas de base (condition d'arrêt) et un cas récursif.

Diviser pour régner (Divide and Conquer)

Une stratégie de résolution de problèmes qui décompose un problème complexe en sous-problèmes plus petits, les résout de manière récursive, puis combine les résultats.

Tri par fusion (Merge Sort)

Un algorithme basé sur la stratégie "Diviser pour régner" qui divise le tableau en deux moitiés, les trie récursivement, puis les fusionne.

Complexité temporelle du tri par fusion

Elle est de $O(n \text{log}(n))$ pour les meilleurs, moyens et pires cas.

Complexité spatiale du tri par fusion

Elle est de $O(n)$, car l'algorithme nécessite de l'espace supplémentaire pour les tableaux temporaires lors de l'étape de fusion.

Tri rapide (Quick Sort)

Un algorithme de tri utilisant la stratégie "Diviser pour régner" et reposant sur le concept de partitionnement pour réorganiser les éléments.

Partitionnement

Le processus de réorganisation d'un tableau dans le tri rapide de sorte que tous les éléments inférieurs au pivot aillent à gauche et les éléments supérieurs à droite.

Pivot

Un élément choisi dans le tableau (souvent l'élément le plus à droite) utilisé comme référence pour diviser les données lors du partitionnement.

Complexité temporelle du tri rapide (Pire cas)

Elle est de $O(n^2)$, ce qui se produit généralement avec une mauvaise sélection du pivot ou un tableau déjà trié.

Complexité spatiale du tri rapide (Cas moyen)

Elle est de $O(n \text{log}(n))$, principalement due à l'utilisation de la pile d'appels récursifs (Call Stack).

Avantage du tri par fusion sur le tri rapide

Le tri par fusion garantit une performance de $O(n \text{log}(n))$ dans tous les cas et préserve l'ordre des éléments égaux (stabilité), contrairement au pire cas du tri rapide.