Tri rapide
Principe
Dans un tri rapide, on va utiliser deux principes. Le premier à déjà été utilisé dans le tri fusion et est de diviser le tableau pour mieux le trié. Le deuxième principe va être de classer les éléments en deux groupes; plus petit et plus grand qu'une valeur pivot. On trira récursivement les deux groupes ainsi triés.
Complexite
Pour ce tri, je ne fournirai pas d'algo ni d'implémentation pour le moment, car si vous en cherchez, vous en trouverez sans aucun probleme sur www.google.com :). ou encore un grep de la fonction qsort de la libc
Le tri rapide a une compléxité worstcase de o(N2) mais de o(N*log2(N)) en moyenne