Algorithme de tri rapide Fermé

Question

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...

8412 · Accepted Answer

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

julplemet · Answer

Salut,
Sans voir le code, c'est un pti peu difficile...

8412 · Answer

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.

julplemet · Answer

Parfait, tu peux mettre ton sujet en résolu.

Algorithme de tri rapide

4 réponses

Discussions similaires