Le drapeau
Énoncé
On va revenir sur l'exercice du pivot déjà traité dans une séance précédente en implantant une variante très connue dite du « drapeau » (souvent hollandais mais ça marche avec plein d'autres !)
La différence avec l'algorithme du pivot est qu'à la fin de la boucle, le tableau doit être divisé en 3 zones :
- la partie de gauche contenant les éléments strictement inférieurs au pivot ;
- la partie du milieu contenant les éléments égaux au pivot ;
- la partie de droite contenant les éléments strictement supérieurs au pivot.
La fonction à écrire a pour prototype drapeau(tab, idx_pivot) et renvoie deux indices :
deb_piv est l'indice de la première case contenant une valeur égale au pivot ;fin_piv est l'indice de la dernière case contenant une valeur égale au pivot.
On travaillera sur un tableau statique et en place sans allouer de tableau intermédiaire. On pourra utiliser le programme principal suivant pour tester notre fonction.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | #!/usr/bin/env python3
"""
Pivot
"""
from random import randint
TAILLE = 20
def echanger(tab, idx1, idx2):
"""
Echange tab[idx1] et tab[idx2]
"""
tmp = tab[idx1]
tab[idx1] = tab[idx2]
tab[idx2] = tmp
def main():
"""
Fonction principale
"""
tab = [randint(0, 10) for _ in range(TAILLE)]
idx_pivot = randint(0, TAILLE - 1)
print("Tableau initial :", tab)
print("Indice du pivot : ", idx_pivot, ", valeur du pivot : ",
tab[idx_pivot], sep="")
print("Drapeau en place :")
deb_piv, fin_piv = drapeau(tab, idx_pivot)
print(" indices du pivot : de", deb_piv, "à", fin_piv)
print(" tableau réorganisé :", tab[0:deb_piv], tab[deb_piv:fin_piv + 1], tab[fin_piv + 1:])
main()
|
Correction
Cliquez ici pour révéler la correction.
drapeau.py :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53 | #!/usr/bin/env python3
"""
Pivot
"""
from random import randint
TAILLE = 20
def echanger(tab, idx1, idx2):
"""
Echange tab[idx1] et tab[idx2]
"""
tmp = tab[idx1]
tab[idx1] = tab[idx2]
tab[idx2] = tmp
def drapeau(tab, idx_pivot):
"""
Version 3 : drapeau en place
"""
val_pivot = tab[idx_pivot]
echanger(tab, 0, idx_pivot)
idx_pivot = 0
prem = 1
dern = len(tab) - 1
while prem <= dern:
if tab[prem] < val_pivot:
echanger(tab, prem, idx_pivot)
idx_pivot += 1
prem += 1
elif tab[prem] == val_pivot:
prem += 1
else:
echanger(tab, prem, dern)
dern -= 1
return idx_pivot, dern
def main():
"""
Fonction principale
"""
tab = [randint(0, 10) for _ in range(TAILLE)]
idx_pivot = randint(0, TAILLE - 1)
print("Tableau initial :", tab)
print("Indice du pivot : ", idx_pivot, ", valeur du pivot : ",
tab[idx_pivot], sep="")
print("Drapeau en place :")
deb_piv, fin_piv = drapeau(tab, idx_pivot)
print(" indices du pivot : de", deb_piv, "à", fin_piv)
print(" tableau réorganisé :", tab[0:deb_piv], tab[deb_piv:fin_piv + 1], tab[fin_piv + 1:])
main()
|
