Partition autour d'un pivot
On se donne un tableau nombres non-vide ne contenant que des nombres entiers.
On souhaite réaliser une partition de ce tableau autour d'une certaine valeur appelée « pivot ». Une fois ce « tri » effectué, le tableau comportera dans l'ordre :
- toutes les valeurs strictement inférieures au pivot,
- toutes les valeurs égales au pivot,
- toutes les valeurs strictement supérieures au pivot.
Il s'agit d'une partition et non d'un tri, car la première et la dernière zone ne sont pas nécessairement triées.
Par exemple, la partition de [3, 0, 2, 1, 5, 1] autour de la valeur pivot 1 donnera [0, 1, 1, 5, 2, 3].
Pour ce faire, on crée et l'on maintient quatre zones dans le tableau :
-
la première zone ne contient que des valeurs strictement inférieures au pivot (en bleu ci-dessous),
-
la deuxième que des valeurs égales au pivot,
- la troisième contient les valeurs mal placées (en gris),
- la dernière zone ne contient que des valeurs strictement supérieures au pivot (en rouge).
Ces zones sont délimitées par les bornes suivantes (incluses) :
- Valeurs strictement inférieures au pivot : de l'indice
0àdebut - 1, - Valeurs égales au pivot : de
debutàmilieu - 1, - Valeurs mal placées : de
milieuàfin, - Valeurs strictement supérieures au pivot : de
fin + 1àlen(nombres) - 1
Au fil de l'algorithme, la zone contenant les valeurs mal placées rétrécit. L'algorithme se termine lorsqu'elle est vide.
L'algorithme à coder est donc le suivant
- on crée une variable
debutégale à0, - on crée une variable
milieuégale à0, - on crée une variable
finégale au dernier indice denombres, - on répète les étapes ci-dessous tant que
milieuest inférieur ou égal àfin:- si la valeur d'indice
milieuest strictement inférieure au pivot, on l'échange avec celle d'indicedebutet l'on incrémentedebutetmilieu, - si elle est égale au pivot, on incrémente
milieu, - sinon, elle est strictement supérieure au pivot : on l'échange avec celle d'indice
finet l'on décrémentefin.
- si la valeur d'indice
Dans l'état initial aucun nombre n'a été trié.
debut = 0milieu = 0fin = 5
On a échangé les valeurs d'indices 0 et 5. fin a été décrémenté.
debut = 0milieu = 0fin = 4
On a échangé les valeurs d'indices 0 et 1. milieu a été incrémenté.
debut = 0milieu = 1fin = 4
On a échangé les valeurs d'indices 1 et 0. debut et milieu ont été incrémentés.
debut = 1milieu = 2fin = 4
On a échangé les valeurs d'indices 2 et 4. fin a été décrémenté.
debut = 1milieu = 2fin = 3
On a échangé les valeurs d'indices 2 et 3. fin a été décrémenté.
debut = 1milieu = 2fin = 2
On a échangé les valeurs d'indices 2 et 2. milieu a été incrémenté.
debut = 1milieu = 3fin = 2
milieu est désormais strictement supérieur à fin. On sort de la boucle.
Échange de valeurs
Il est possible d'échanger deux valeurs d'indices i et j en faisant nombres[i], nombres[j] = nombres[j], nombres[i].
Fonctions, opérateurs ou modules interdits
Dans cet exercice on interdit d'utiliser :
-
sorted -
list.sort
Exemples
>>> # Le pivot est 1
>>> nombres = [3, 0, 2, 1, 5, 1]
>>> tri_pivot(nombres, 1)
>>> nombres
[0, 1, 1, 5, 2, 3]
Les trois zones sont [0], [1, 1] et [5, 2, 3].
>>> # Le pivot est 7
>>> nombres = [7, 2, 5, 5, 9, 1, 9, 7, 2, 5]
>>> tri_pivot(nombres, 7)
>>> nombres
[2, 5, 5, 5, 1, 2, 7, 7, 9, 9]
Les trois zones sont [2, 5, 5, 5, 1, 2], [7, 7] et [9, 9].
Écrire la procédure partition qui prend en paramètres un tableau de nombres entiers et un entier représentant la valeur du pivot, et qui modifie en place le tableau.
Rappel : procédure
Une procédure est une fonction qui ne renvoie rien.
En python, même si une fonction ne contient pas le mot-clé return, elle renverra toujours par défaut l'objet None.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)