# Programmation algorithmique/Tris

* Introduction
* Nombre d'opérations optimal
* Mathématiques simples
* Tableaux : parcours, recherches
* Tris de tableaux
* Structures de données
** Listes simplement chaînées
** Listes doublement chaînées
** Arbres
* Introduction
* Nombre d'opérations optimal
* Mathématiques simples
* Tableaux : parcours, recherches
* Tris de tableaux
* Structures de données
** Listes simplement chaînées
** Listes doublement chaînées
** Arbres
[ Modifier le sommaire ]
Les algorithmes de tri vise à ordonnancer une séquence, en suivant un ordre total. Pour pouvoir être trié avec ces algorithmes, un ordre doit donc être établi sur les éléments à trier.
Cet ordre est implicite pour des entiers, il peut l'être moins sur des données plus complexes comme par exemple des nombres flottants ou des textes.

## Les algorithmes de tri
### Tri par sélection

* Paramètre en entrée/sortie : Un tableau t de N entiers T[1..N];
* Spécifications : en sortie t doit être trié du plus petit au plus grand.
* Intuition : On cherche (on sélectionne) le plus petit élément du tableau et on le place en début de tableau, puis on cherche le plus petit élément dans le reste du tableau et on le place en seconde position dans le tableau, et ainsi de suite.
* Complexité en temps: $O(n^{2})$

### Tri bulle

* Paramètre en entrée/sortie : Un tableau t de N entiers T[1..N];
* Spécifications : en sortie t doit être trié du plus petit au plus grand.

### Tri par insertion

Paramètre en entrée/sortie : Un tableau t de N entiers T[0..N]

### Tri rapide

On choisit le pivot de manière aléatoire dans le tableau. Ensuite on inverse le pivot de sa position à celle du premier élément du tableau (indice 1) puis on fait une comparaison avec tous les éléments du tableau. S'il y a un élément du tableau qui lui est supérieur, alors il y a échange des éléments. Cette comparaison s'arrêtera quand l'indice gauche du tableau (ici i) sera plus grand que l'indice droit du tableau (ici j). Après cet arrêt de la fonction Partitionner, on retourne l'indice j et on rappel la procédure Tri_rapide
* Complexité en espace : En raison des appels récursif, on a besoin d'une pile dont la taille est en $O(log(n))$.
* Complexité en temps : $O(n.log(n))$ en moyenne, $O(n^{2})$ dans le pire cas.
* Nom anglais : quicksort.

### Tri fusion

* Complexité en temps : $O(n.log(n))$
* Nom anglais : merge sort.

### Tri par tas

* Complexité en temps : $O(n.log(n))$
* Nom anglais : heapsort.

### Tri de Shell

* Complexité en temps : la complexité en temps de ce tri dépend de son paramétrage et, selon les cas, on trouve $O(n^{2})$, $O(n^{3/2})$, ou $O(n^{4/3})$ par exemple. Voir w:Shellsort, w:Tri_de_Shell ou The art of Computer Programming volume 3, Donald E. Knuth, Addison-Wesley.

## Tri de fichiers en mémoire externe

Cette section concerne le tri de données trop grandes pour être stockées en mémoire vive de l'ordinateur, et étant donc stockées sur des supports physiques comme des disques durs.
Notons que les périphériques de stockage sont généralement plus lents que la mémoire vive. Par ailleurs, autrefois le support externe de référence était la bande magnétique, avec pour résultat que le temps d'accès à une donnée dépend de sa position sur la bande, alors qu'en mémoire vive, le temps d'accès aux données ne dépend pas de leur emplacement (si l'on fait abstraction des questions de mémoire tampon).