Skip to content

TP11. Pivot

Énoncé

On se propose d'implémenter un algorithme qui partitionne un tableau en 2 autour d'un élément dit pivot. La partition gauche, contient tous les éléments inférieurs ou égaux au pivot. La partition droite, contient tous les éléments supérieurs au pivot.

Notre algorithme prendra en entrée un tableau de n entiers ainsi que l'indice de la case du tableau contenant le pivot.

Pivot avec nouveaux tableaux dynamiques

Dans un premier temps, implémentez une fonction pivote(tableau, indice_pivot) renvoyant deux tableaux dynamiques (on s'autorise donc à utiliser append):

  • le premier contient tous les éléments inférieurs ou égaux au pivot ;
  • le second contient tous les éléments supérieurs au pivot ;
  • le pivot lui même n’appartient à aucun des tableaux renvoyés.

Il y a en général de nombreuses possibilités de solutions, l'ordre entre les "petits" (respectivement les "grands") n'étant pas contraint.

Par exemple, si on appelle pivote(tab, 0) et que tab est le tableau suivant tableau d'entrée

alors un résultat correct serait :

partition gauche partition droite

Pivot en place

Dans un second temps, on se propose de travailler en place. Au lieu de renvoyer deux tableaux dynamiques, on déplace directement les éléments du tableau d'entrée en procédant par échanges. Le pivot doit se retrouver entre les deux parties du tableau. On vous demande de ne pas utiliser de tableaux additionnels.

Attention cette implémentation est difficile et nécessite sans doute d'essayer sur papier avant de commencer et de réfléchir aux invariants de boucle.

Toujours sur le même tableau d'entrée, un résultat correct de pivote(tab, 0) serait :

résultat en place

Difficulté

star star star star

Exercices associés