Algorithmes de tri

L'algorithme de tri le plus basique qui compare à plusieurs reprises les éléments adjacents et les échange s'ils sont dans le mauvais ordre. Comme des bulles qui remontent à la surface, les valeurs plus grandes se déplacent progressivement vers la fin du tableau. Idéal pour les petits ensembles de données ou à des fins éducatives pour comprendre les fondamentaux du tri.

Trouve l'élément le plus petit et le déplace à l'avant de manière répétée. Chaque itération « sélectionne » le minimum parmi les éléments restants et le place après la partie triée. Simple à implémenter avec une utilisation minimale de la mémoire, mais prend toujours un temps O(n²) quelle que soit l'entrée.

Un algorithme de tri hautement efficace qui sélectionne un élément pivot et partitionne le tableau avec les valeurs plus petites à gauche et les plus grandes à droite. En moyenne O(n log n) et c'est la méthode de tri la plus utilisée en pratique. Forme la base des fonctions de tri intégrées dans la plupart des langages de programmation.

Utilise une structure de données de tas binaire en construisant d'abord un tas maximum, puis en extrayant à plusieurs reprises l'élément racine pour trier. Garantit une complexité temporelle O(n log n) dans tous les cas sans nécessiter de mémoire supplémentaire. Sert également de base aux implémentations de file de priorité.

Un algorithme de tri non comparatif qui compte les occurrences de chaque élément et utilise l'arithmétique pour déterminer les positions. Atteint une complexité temporelle O(n+k) où k est la plage des valeurs d'entrée. Idéal pour trier des entiers dans une plage connue et limitée. Forme la base du tri par base.

Un algorithme de tri non comparatif qui traite les éléments chiffre par chiffre du moins significatif au plus significatif. Utilise le tri par comptage comme sous-routine pour chaque position de chiffre. Atteint un temps O(d(n+k)) où d est le nombre de chiffres. Excellent pour trier des entiers ou des chaînes de longueur fixe.

Une optimisation du tri par insertion qui permet l'échange d'éléments éloignés. Utilise une séquence d'écarts qui diminue jusqu'à 1, permettant à l'algorithme de déplacer les éléments plus près de leurs positions finales plus rapidement. Nommé d'après Donald Shell qui l'a inventé en 1959.

Un algorithme de tri basé sur la distribution qui distribue les éléments dans un certain nombre de seaux. Chaque seau est ensuite trié individuellement en utilisant un autre algorithme de tri. Fonctionne mieux lorsque l'entrée est uniformément distribuée sur une plage. La complexité temporelle moyenne est O(n+k).

Un algorithme de division et conquête qui divise le tableau en deux, trie chaque moitié de manière récursive, puis les fusionne ensemble. Garantit un temps O(n log n) et est stable, mais nécessite de la mémoire supplémentaire. Particulièrement efficace pour les grands ensembles de données et le tri de listes chaînées.

Fonctionne comme le tri de cartes à jouer dans vos mains - insérant chaque élément un à la fois à sa position appropriée. S'exécute en temps O(n) pour les données déjà triées, ce qui le rend très efficace pour les petits tableaux ou les ensembles de données presque triés. Algorithme simple mais adaptatif.

Amélioration du tri à bulles qui élimine les petites valeurs près de la fin de la liste (tortues). Utilise une séquence d'écart décroissant commençant par la longueur du tableau, améliorant la complexité du pire cas. Pratique pour les ensembles de données de taille moyenne où une implémentation simple est valorisée par rapport aux performances optimales.

Algorithme de tri simple similaire au tri par insertion, nommé d'après la façon dont les gnomes de jardin trient les pots de fleurs. Recule lorsque les éléments sont dans le désordre, puis avance à nouveau. Bien que O(n²) comme le tri à bulles, sa simplicité le rend utile pour enseigner les concepts de tri et gérer de petits ensembles de données.