Algorithme de tri rapide
8412
-
julplemet Messages postés 331 Date d'inscription Statut Membre Dernière intervention -
julplemet Messages postés 331 Date d'inscription Statut Membre Dernière intervention -
Salut ! J'ai un problème pour implémenter un algo de tri rapide : à partir du moment où j'ai 3 valeurs égales dans mon tableau, l'algorithme finit par tourner en boucle infinie... En effet, dès qu'une itération de cette valeur devient pivot, les 2 autres s'échangent à l'infini.
Comment remédier à ce problème en restant dans la logique du tri rapide ?
Merci d'avance...
Comment remédier à ce problème en restant dans la logique du tri rapide ?
Merci d'avance...
A voir également:
- Algorithme de tri rapide
- Acces rapide - Guide
- Comment faire un tri personnalisé sur excel - Guide
- Logiciel tri photo - Guide
- Copie rapide - Télécharger - Gestion de fichiers
- Telechargement rapide - Télécharger - Téléchargement & Transfert
4 réponses
C'est bon, j'ai résolu mon problème. Pour ceux que ça intéresserait éventuellement un jour, il suffit d'incrémenter i (et décrémenter j) après l'échange de data[i] et data[j]. Ainsi, on échange jamais deux fois le même couple de valeurs. Merci quand même : p
def tri_rapide_interne(data, gauche, droite):
if droite >= gauche:
pivot = data[droite]
i = gauche
j = droite -1
while True:
while data[i] < pivot:
i = i + 1
while j > 0 and data[j] > pivot:
j = j - 1
if i >= j:
break
echanger(data, i, j)
echanger(data, i, droite)
tri_rapide_interne(data, gauche, i-1)
tri_rapide_interne(data, i + 1, droite)
return data
return data
def tri_rapide(data, size):
"""Tri rapide
"""
data = tri_rapide_interne(data, 0, size-1)
return data
En effet, désolé... voilà le code.
