Discussion :

[chester119]

salut a ts
je suis débutant en matiére de programmation, je viens de connaitre la quick sort, j'ai trouvé plusieurs algorithmes sur le net mais j'ai pas trés bien compri la méthode de ce tri, il s'avére qu'il est le plus rapide donc je voudrais bien avoir une aide sur cette méthode de tri.
merci

[Pacorabanix]

il veut comprendre l'algorithme je crois. Si c'est cela ta question aura plus de sens dans le forum algorithme, et non le forum C++ .

(une petite remarque :
Attention le quicksort est le plus rapide en *moyenne*, mais il est suivi de près par *le tri par fusion* (meme complexité asymptotique). La différence est que le tri "rapide" devient EXTREMEMENT lent si le tableau est deja trié ou trié en ordre inverse)


Voici une explication :

Le tri du tableau se fait en fait par choix d'un *pivot* (le choix de ce pivot fait la qualité de l'algorithme) qui va séparer les données en 2 moitié : les données plus petite et les données plus grandes. Ensuite c'est du tri par insertion je crois, couplé au fait que pour chaque moitié on réapplique le principe : on choisit un pivot qui va séparer la partie à trier en 2 moitiés.

je trouve que cette annimation de l'article wikipedia est pas mal pour comprendre la subtilité :
http://en.wikipedia.org/wiki/Quicksort