On aligne $n$ boules, réparties en un nombre quelconque de boules de couleur bleue, blanche ou rouge.
Ces boules sont disposees dans un ordre quelconque. La ligne de boules est representée par un tableau B de taille $n$, dont chaque ́element B[i] appartient à l’ensemble {bleu, blanc, rouge}
Question : ́Ecrire un algorithme qui trie le tableau de telle facon que toutes les boules bleues apparaissent au debut, suivies des boules blanches puis des boules rouges. La contrainte est que le tri du tableau doit être realise en seul parcours (on ne peut tester qu’une seule fois la couleur de chaque boule) et en place (sans utiliser de deuxieme tableau).
Indication : Les elements d’un tableau peuvent être réécrits.
D'abord, quelques exemples de tableaux.
BLEU, BLANC, ROUGE = "bleu", "blanc", "rouge"
boules1 = [BLEU, BLANC, ROUGE, ROUGE, BLANC, BLEU, BLANC, ROUGE, BLANC, BLEU, ROUGE]
boules2 = [BLEU, BLANC, ROUGE, ROUGE, BLANC, BLEU, BLANC, ROUGE, BLANC, BLEU, ROUGE][::-1]
boules3 = boules2 *2 + boules1 * 2
Et des cas spéciaux, sans forcément avoir des boules de chaque couleurs :
boules4 = [BLEU, BLANC, BLEU, BLANC, BLEU, BLANC, BLEU, BLANC, BLEU, BLANC, BLEU, BLANC] # pas de rouges
boules5 = [BLANC, ROUGE, BLANC, ROUGE, BLANC, ROUGE, BLANC, ROUGE, BLANC, ROUGE, BLANC, ROUGE] # pas de bleues
boules6 = [ROUGE, BLEU, ROUGE, BLEU, ROUGE, BLEU, ROUGE, BLEU, ROUGE, BLEU, ROUGE, BLEU, ROUGE, BLEU] # pas de blanches
boules7 = [BLEU] * 20 # que des bleues
boules8 = [BLANC] * 20 # que des blanches
boules9 = [ROUGE] * 20 # que des rouges
Juste pour faire joli, je vais écrire des fonctions qui soient "typées" en Python, c'est-à-dire avec des indications de types. Python reste un langage dynamiquement typé, ces indications seront JUSTE là pour faire joli.
from typing import List, Union
Boule = Union["bleu", "blanc", "rouge"]
Boules = List[Boule]
Visualisation : je vais utiliser le petit module ipythonblocks :
from ipythonblocks import BlockGrid
c_bleu, c_blanc, c_rouge = (0, 0, 255), (215, 215, 215), (255, 0, 0)
def boules_vers_grid(boules: Boules) -> BlockGrid:
n = len(boules)
grid = BlockGrid(n, 1, fill=(c_blanc))
for i, boule in enumerate(boules):
if boule == BLEU:
grid[0,i].set_colors(*c_bleu)
elif boule == BLANC:
grid[0,i].set_colors(*c_blanc)
elif boule == ROUGE:
grid[0,i].set_colors(*c_rouge)
return grid
def print_boules(boules: Boules) -> None:
boules_vers_grid(boules).show()
print_boules(boules1)
print_boules(boules2)
print_boules(boules3)
print_boules(boules4)
print_boules(boules5)
print_boules(boules6)
print_boules(boules7)
print_boules(boules8)
print_boules(boules9)
sorted ou un tri écrit à la main¶def echange(tab: List, i: int, j: int) -> None:
tab[i], tab[j] = tab[j], tab[i]
def comparaison_couleur(boule1: Boule, boule2: Boule) -> int:
""" Renvoie +1 si boule1 > boule2, 0 si =, -1 si <."""
b1, b2 = boule1, boule2
if b1 == b2:
return 0
elif b1 == BLEU:
return -1
elif b1 == BLANC:
if b2 == BLEU:
return +1
elif b2 == ROUGE:
return -1
elif b1 == ROUGE:
return +1
import itertools
for boule1, boule2 in itertools.product([BLEU, BLANC, ROUGE], repeat=2):
print(f"Comparaison {boule1:>5} et {boule2:>5} = {comparaison_couleur(boule1, boule2)}")
Comparaison bleu et bleu = 0 Comparaison bleu et blanc = -1 Comparaison bleu et rouge = -1 Comparaison blanc et bleu = 1 Comparaison blanc et blanc = 0 Comparaison blanc et rouge = -1 Comparaison rouge et bleu = 1 Comparaison rouge et blanc = 1 Comparaison rouge et rouge = 0
def tri_a_bulle(boules: Boules) -> Boules:
b = boules[:]
n = len(b)
for i in range(n - 1, -1, -1):
for j in range(0, i):
if comparaison_couleur(b[j+1], b[j]) < 0:
echange(b, j+1, j)
print_boules(b)
return b
tri_a_bulle(boules1)
['bleu', 'bleu', 'bleu', 'blanc', 'blanc', 'blanc', 'blanc', 'rouge', 'rouge', 'rouge', 'rouge']
tri_a_bulle(boules2)
['bleu', 'bleu', 'bleu', 'blanc', 'blanc', 'blanc', 'blanc', 'rouge', 'rouge', 'rouge', 'rouge']
tri_a_bulle(boules3)
['bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge']
Ici, on connaît le domaine des valeurs, qui est de taille 3 (trois couleurs). Le tri comptage va faire une seule passe sur le tableau d'entrée, et compter combien de boules de chaque couleurs sont présentes, puis réécrire le tableau de sortie en écrivant le bon nombre de boules bleues, puis blanches, puis rouges.
def tri_comptage(boules: Boules) -> Boules:
n = len(boules)
comptages = {BLEU: 0, BLANC: 0, ROUGE: 0}
for boule in boules:
comptages[boule] += 1
# exactement un seul parcours du tableau
b = [None] * n
nb_bleu, nb_blanc, nb_rouge = comptages[BLEU], comptages[BLANC], comptages[ROUGE]
print(f"En une seule passe du tableau, on a compté {nb_bleu} boule(s) bleue(s), {nb_blanc} boule(s) blanche(s), {nb_rouge} boule(s) rouge(s).")
boule_actuelle = BLEU
if nb_bleu == 0:
boule_actuelle = BLANC
if nb_blanc == 0:
boule_actuelle = ROUGE
# et exactement un seul parcours du tableau de destination
for i in range(0, n):
b[i] = boule_actuelle
print_boules(b[:i + 1])
if i + 1 >= nb_bleu + nb_blanc:
boule_actuelle = ROUGE
elif i + 1 >= nb_bleu:
boule_actuelle = BLANC
# note en Python on aurait pu faire
b2 = ([BLEU] * nb_bleu) + ([BLANC] * nb_blanc) + ([ROUGE] * nb_rouge)
assert b == b2
return b
print_boules(boules1)
tri_comptage(boules1)
En une seule passe du tableau, on a compté 3 boule(s) bleue(s), 4 boule(s) blanche(s), 4 boule(s) rouge(s).
['bleu', 'bleu', 'bleu', 'blanc', 'blanc', 'blanc', 'blanc', 'rouge', 'rouge', 'rouge', 'rouge']
print_boules(boules2)
tri_comptage(boules2)
En une seule passe du tableau, on a compté 3 boule(s) bleue(s), 4 boule(s) blanche(s), 4 boule(s) rouge(s).
['bleu', 'bleu', 'bleu', 'blanc', 'blanc', 'blanc', 'blanc', 'rouge', 'rouge', 'rouge', 'rouge']
print_boules(boules3)
tri_comptage(boules3)
En une seule passe du tableau, on a compté 12 boule(s) bleue(s), 16 boule(s) blanche(s), 16 boule(s) rouge(s).
['bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge']
Autres exemples :
print_boules(boules4)
tri_comptage(boules4)
En une seule passe du tableau, on a compté 6 boule(s) bleue(s), 6 boule(s) blanche(s), 0 boule(s) rouge(s).
['bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc']
print_boules(boules5)
tri_comptage(boules5)
En une seule passe du tableau, on a compté 0 boule(s) bleue(s), 6 boule(s) blanche(s), 6 boule(s) rouge(s).
['blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge']
print_boules(boules6)
tri_comptage(boules6)
En une seule passe du tableau, on a compté 7 boule(s) bleue(s), 0 boule(s) blanche(s), 7 boule(s) rouge(s).
['bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge']
Encore des exemples :
print_boules(boules7)
tri_comptage(boules7)
En une seule passe du tableau, on a compté 20 boule(s) bleue(s), 0 boule(s) blanche(s), 0 boule(s) rouge(s).
['bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu', 'bleu']
print_boules(boules8)
tri_comptage(boules8)
En une seule passe du tableau, on a compté 0 boule(s) bleue(s), 20 boule(s) blanche(s), 0 boule(s) rouge(s).
['blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc', 'blanc']
print_boules(boules9)
tri_comptage(boules9)
En une seule passe du tableau, on a compté 0 boule(s) bleue(s), 0 boule(s) blanche(s), 20 boule(s) rouge(s).
['rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge', 'rouge']
Voilà.