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
alors un résultat correct serait :
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 :
Cliquez ici pour révéler la correction.
Correction
Une correction détaillée en deux vidéos est disponible :
Difficulté
