3.1 Pivot

On se propose implémenter un algorithme de pivot de différentes façons.

On a en entrée un tableau de n éléments comparables ainsi que l’indice d’une case du tableau contenant le pivot. On souhaite déplacer les éléments du tableau en les comparant au pivot.

Dans un premier temps, implémentez une fonction pivote(tableau, indice_pivot) renvoyant deux tableaux  : le premier contient tous les éléments inférieurs ou égaux au pivot, le second 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" (resp. les "grands") n’étant pas contraint.

Dans un second temps, on se propose de travailler en place. Au lieu de renvoyer deux tableaux, on déplace directement les éléments du tableau d’entrée (en procédant par échanges). On vous demande de ne pas utiliser de tableaux additionnels. Attention cette implémentation est difficile et nécessite sans doute d’essayer un peu sur papier avant de commencer.