Sorting Algorithm

Les algorithmes de tri arrangent les éléments en ordre — tri rapide, tri fusion et tri par tas sont courants — avec des complexités allant de O(n log n) à O(n²).

Objectif

Mettre de l'ordre dans les données non triées, socle de la recherche, de la déduplication et de l'affichage.

Mécanisme

Le tri par comparaison a une borne inférieure O(n log n). Le tri rapide est en moyenne O(n log n), au pire O(n²), en place. Le tri fusion est O(n log n), stable, mais exige O(n) d'espace. Le tri par tas est O(n log n) en place. Les tris par comptage/radix sont non comparatifs et peuvent atteindre O(n). Les tris stables préservent l'ordre relatif des éléments égaux.

Cas d’usage

ORDER BY en bases de données
Prétraitement avant recherche
Classements et palmarès
Déduplication (tri + comparaison adjacente)

Exemples

entrée
```
[3,1,4,1,5] → quicksort
```
Output
```
[1,1,3,4,5]
```
O(n log n) average

Erreurs courantes

Quicksort recursion overhead is high for small arrays: Use insertion sort for small arrays (a quicksort optimization)

Termes associés

La notation grand O décrit la borne supérieure asymptotique d'une fonction, utilisée pour analyser la complexité temporelle/spatiale des algorithmes en ignorant les constantes et les termes d'ordre inférieur.

La recherche dichotomique compare avec l'élément central d'un tableau trié et divise l'intervalle par deux à chaque étape, localisant une cible en O(log n) ; c'est l'algorithme de recherche efficace fondateur.

Une table de hachage associe des clés à un tableau de compartiments via une fonction de hachage, offrant recherche/insertion/suppression en O(1) en moyenne ; c'est l'une des structures de données les plus utilisées.

Outils associés

Trier et dédupliquer

Sort lines alphabetically, numerically, by length, or naturally; deduplicate; reverse or shuffle. Gratuit, privé et 100% côté client.

References