Tri rapide

Version imprimable

06/12/2004, 17h12
DBBB

Tri rapide

Slt! :D

Je voudrais réaliser un "tri rapide". J'ai lut une explication la dessus seulement je n'ais pas trop compris d'autant qu'il n'ait pas expliquer coment faire en cas d'un nombre de nombre impair et surtout en cas de deux nombre égaux.

Est-ce que quelqu'un pourrait m'expliquer SVP?

A+! :D
06/12/2004, 19h05
PINGOUIN_GEANT

Re: Tri rapide

Citation:

Envoyé par DBBB

Je voudrais réaliser un "tri rapide".
...
coment faire en cas d'un nombre de nombre impair

je suppose que c'est le tri fusion, tu prends la partie entière, quand tu divises

Citation:

Envoyé par DBBB

et surtout en cas de deux nombre égaux.

je ne vois pas où est le problème :
que tu tries en mettant 1 1 ou 1 1 c'est pareil
s'il n'y a que ces deux points, cela devrait aller pour programmer.
06/12/2004, 22h48
Nicodemus

Je ne crois pas qu'il parle du tri fusion, mais bel et bien du tri rapide ou plutôt du quick sort. Il n'y a pas grand chose à comprendre là dessus. De toute façon l'algo est disponible en pseudo-langage et dans un paquet de langages de programmation sur le net.

:google: , c'est ton ami :lol:
06/12/2004, 23h02
PINGOUIN_GEANT

sauf erreur de ma part il n'y pas d'histoire de parité dans le tri rapide vu qu'on utilise un pivot
06/12/2004, 23h23
Mac LAK

Citation:

Envoyé par PINGOUIN_GEANT

sauf erreur de ma part il n'y pas d'histoire de parité dans le tri rapide vu qu'on utilise un pivot

L'algo "classique" te dit de séparer ton tableau en deux parties égales, ce qui perturbe souvent les débutants lorsque le tableau est de cardinalité impaire.

:fleche: DBBB : En cas de cardinalité impaire, tu fais un arrondi : une des parties aura un élément de plus que l'autre, c'est tout, et ça ne changera pas le résultat final.
07/12/2004, 11h09
PINGOUIN_GEANT

Citation:

Envoyé par Mac LAK

L'algo "classique" te dit de séparer ton tableau en deux parties égales, ce qui perturbe souvent les débutants lorsque le tableau est de cardinalité impaire.

Oui, l'algo classique du tri fusion mais pas du tri rapide ou alors j'ai un problème avec mes classiques.
07/12/2004, 17h59
Jedai

Effectivement, dans le quick sort, on ne divise pas en parties égales, mais selon un pivot, donc pas de problème de parité. Par contre pour la question des nombres égaux au pivot, tu peux soit les ignorer et les considérer comme plus petit (ou plus grand), tout simplement, soit prendre en compte ce cas, avec une petite amélioration du quick sort, intéressant pour certains types de tableaux. Je crois qu'une petite recherche sur "algorithme drapeau hollandais" sur Google pourrait t'aider. :D

--
Jedaï
07/12/2004, 18h21
Mac LAK

Citation:

Envoyé par PINGOUIN_GEANT

Oui, l'algo classique du tri fusion mais pas du tri rapide ou alors j'ai un problème avec mes classiques.

On te dit te prendre ton pivot au milieu du tableau, ce qui revient à découper en deux parties égales. Tout dépend de la manière dont on t'a expliqué le quick sort, moi c'était la variante récursive.
08/12/2004, 20h47
Jedai

Tu peux prendre le pivot au milieu, mais tu peux aussi le prendre à la fin, ou au début, statistiquement ça n'a aucune importance et c'est plus commode...
Après ça dépend de tes données : si tu penses que ton tableau est déjà presque trié, il vaut sans doute mieux prendre un nombre au milieu du tableau, mais du poit de vue de l'algorithme, cela n'a strictement aucunement importance.

--
Jedaï
10/12/2004, 09h49
Catbull

Citation:

Envoyé par Mac LAK

Citation:

Envoyé par PINGOUIN_GEANT

Oui, l'algo classique du tri fusion mais pas du tri rapide ou alors j'ai un problème avec mes classiques.

On te dit te prendre ton pivot au milieu du tableau, ce qui revient à découper en deux parties égales. Tout dépend de la manière dont on t'a expliqué le quick sort, moi c'était la variante récursive.

Cela ne sert à rien de vouloir prendre le pivot au milieu du tableau. La meilleur valeur pour le pivot et la valeur qui va permettre de placer autant de valeur à gauche qu'a droite du pivot. Or cette valeur n'est pas connue.

Une stratégie classique pour chosir un pivot c'est de sélectionner trois valeurs et de prendre la valeur intermédiaire...
10/12/2004, 11h50
Mac LAK

Citation:

Envoyé par Catbull

Cela ne sert à rien de vouloir prendre le pivot au milieu du tableau. La meilleur valeur pour le pivot et la valeur qui va permettre de placer autant de valeur à gauche qu'a droite du pivot. Or cette valeur n'est pas connue.

Je sais.

Simplement, et pour finir sur le sujet, je rappelle que pour les débutants, quand on leur dit de partager le tableau en deux, ils pensent plus souvent à le partager suivant la cardinalité (d'où ma remarque sur la parité) que suivant la position de la valeur médiane (qui, comme tu le fais remarquer, n'est pas connue). Cependant, si la distribution du tableau non-trié est homogène et aléatoire, il y a de fortes probabilités que le pivot idéal soit justement près du milieu du tableau.

Bien sûr, cette remarque n'a pas lieu d'être avec des développeurs confirmés, qui ont compris depuis longtemps comment marchent un QuickSort et cherchent en général à l'optimiser ! :D

Pour les débutants, il vaut peut-être mieux qu'ils s'attaquent d'abord à implémenter correctement l'algo dans une forme basique et non-optimisée avant d'attaquer directement les optimisations de tris, tu ne crois pas ? ;-)

Sinon, il aurait fallu lui dire d'abandonner le QuickSort et d'utiliser un tri par casiers... :mrgreen:
10/12/2004, 17h54
PINGOUIN_GEANT

Citation:

Envoyé par Mac LAK

Cependant, si la distribution du tableau non-trié est homogène et aléatoire, il y a de fortes probabilités que le pivot idéal soit justement près du milieu du tableau.

si la répartition des valeurs est aléatoire (loi uniforme), c'est aussi bien de le prendre au début, au milieu ou à la fin.
Par contre, je veux bien croire qu'avec un tabeau presque trié, il vaut mieux prendre au milieu.