Arbre de décision quicksort

Question

Je viens de passer quelques heures à essayer de représenter l'arbre de décision de l'algorithme quicksort sur un ensemble d'éléments (et j'ai aussi cherché sur le web). J'aimerais savoir ce que chaque nœud représente réellement. Est-ce la comparaison entre deux ensembles (résultant de l'appel à Partition)? ou juste la comparaison entre deux éléments de l'ensemble? J'espère que ma question est assez claire.

Answer 1

Cela dépend de ce que vous voulez appeler une décision. Puisque la seule chose qui peut avoir un résultat différent est le choix de l'élément pivot, je pense que chaque bord de votre arbre est un tel choix. Un nœud est donc un tableau partiellement partitionné, avec des marques pour les intervalles à trier. En d'autres termes, vous avez besoin d'une liste d'index de pivot en plus du tableau dans chaque nœud.