Tri rapide, qsort

Bonjour,

Je dois programmer la fonction qsort, mais je ne comprends pas comment elle fonctionne. Quelqu'un pourrait m'expliquer svp ? Sur internet y'a de tout et n'importe quoi.

J'ai compris qu'il faut choisir un pivot. Placer à droite du tableau les elements qui lui sont inférieurs et à gauche les éléments qui lui sont supérieurs. Une fois que c'est fait, on prend un nouveau pivot pour trié la partie droite et idem pour la partie gauche, et recursivement...

Mais sur un exemple je ne vois pas comment ça ce fait, y'a des exemples sur le net mais y'a plein d'étapes de sautées, du coup je ne comprends pas du tout.

Merci

:google: "wiki qsort" :fleche: 1ere entrée

Citation:

---

Envoyé par darkwall_37

Je dois programmer la fonction qsort,

---

La fonction C qsort() est une fonction de tri générique. La norme ne précise pas l'algorithme utilisé.

Peut être veux-tu implémenter un quicksort, ce qui est totalement autre chose.

Il faut commencer par se documenter sur ce qu'est l'algorithme quicksort. Wikipédia est ton amie...

Sinon, il y a un forum 'algorithmes' (et une FAQ) sur ce site.

:google: qsort

1ere entrée
le super site d un éminent intervant du site

Qui a dit fayot ?

Oui je dois refaire la fonction qsort, pas l'utiliser. J'ai déjà lu wiki et tout, mais je n'arrive pas à faire le tri sur un papier manuellement, ce qui m'empêche de le programmer.

Ce que je cherche c'est une âme charitable qui me ferait un exemple de ce tri étape par étape sur 5 entiers par exemple afin que je comprenne. Bien qu'expliquée sur plusieurs sites, je n'arrive pas à faire le tri sur un exemple tout seul.

Merci d'avance

Citation:

---

Envoyé par Emmanuel Delahaye

Il faut commencer par se documenter sur ce qu'est l'algorithme quicksort. Wikipédia est ton amie...

---

Attention, il faut tout de même prendre wikipédia avec des pincettes.
Ils ne disent pas toujours la vérité :s

Si vous voulez vérifier par vous même tapez : Wiki + SHA1 et aller voir le RFC correspondant vous comprendrez :)

a+

Citation:

---

Envoyé par rilou

Attention, il faut tout de même prendre wikipédia avec des pincettes.
Ils ne disent pas toujours la vérité :s

Si vous voulez vérifier par vous même tapez : Wiki + SHA1 et aller voir le RFC correspondant vous comprendrez :)

---

Rien ne t'empêche de corriger si c'est erroné. C'est un média ouvert.

Mon post inutile a été tronqué,

j avais mis une reference sur le site dur zero qui paraissait pas mal.

Je l'ai déjà vu cette source ! elle ne marche pas, erreur mémoire à la compilation. Ou alors je suis vraiment une brank et je ne sais pas m'en servir.

Numerical Recipes

ou, comme l'a dit Emmanuel, n'importe quelle bonne référence sur quickSort

Origin = Epitech :aie: ?

C'est censé m'aider ça ?

oui :D

Comme on l'a dit, l'algorithme de base est le QuickSort

Comme on ne fera pas l'exercice à ta place, on te donne les pointeurs où trouver de l'info.

Ouai bon ok...

Citation:

---

Envoyé par darkwall_37

Ce que je cherche c'est une âme charitable qui me ferait un exemple de ce tri étape par étape sur 5 entiers par exemple afin que je comprenne. Bien qu'expliquée sur plusieurs sites, je n'arrive pas à faire le tri sur un exemple tout seul.

---

c'est de la dichotomie appliquée sur un tri, avec une fonction de comparaison..