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é.

A non-comparison sorting algorithm that counts occurrences of each element and uses arithmetic to determine positions. Achieves O(n+k) time complexity where k is the range of input values. Ideal for sorting integers within a known, limited range. Forms the basis for radix sort.

A non-comparison sorting algorithm that processes elements digit by digit from least significant to most significant. Uses counting sort as a subroutine for each digit position. Achieves O(d(n+k)) time where d is the number of digits. Excellent for sorting integers or fixed-length strings.

An optimization of insertion sort that allows exchange of elements that are far apart. Uses a gap sequence that decreases to 1, enabling the algorithm to move elements closer to their final positions faster. Named after Donald Shell who invented it in 1959.

A distribution-based sorting algorithm that distributes elements into a number of buckets. Each bucket is then sorted individually using another sorting algorithm. Works best when input is uniformly distributed over a range. Average time complexity is 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.

Improvement over bubble sort that eliminates small values near the end of the list (turtles). Uses a shrinking gap sequence starting with array length, improving worst-case complexity. Practical for medium-sized datasets where simple implementation is valued over optimal performance.

Simple sorting algorithm similar to insertion sort, named after the way garden gnomes sort flower pots. Moves backward when elements are out of order, then forward again. While O(n²) like bubble sort, its simplicity makes it useful for teaching sorting concepts and handling small datasets.