Tri d'un tableau de 0 et de 1⚓︎

On considère un tableau d'entiers zeros_et_uns (type list dont les éléments sont des 0 ou des 1). On se propose de trier ce tableau selon l'algorithme suivant : à chaque étape du tri, le tableau est constitué de trois zones consécutives, la première ne contenant que des 0, la seconde n'étant pas triée et la dernière ne contenant que des 1.

Ci-dessous un schéma de la situation pendant le processus de séparation des 0 et des 1 :

📋 Texte

debut de zone            fin de zone
    non triée            non triée
           |              |
           v              v
 ------------------------------------
| 0 ... 0 | zone non triée | 1 ... 1 |
 ------------------------------------

Tant que la zone non triée n'est pas réduite à un seul élément, on regarde son premier élément :

si cet élément vaut 0, on considère qu'il appartient désormais à la zone ne contenant que des 0 ;
si cet élément vaut 1, il est échangé avec le dernier élément de la zone non triée et on considère alors qu'il appartient à la zone ne contenant que des 1.

Dans tous les cas, la longueur de la zone non triée diminue de 1.

Exemples

🐍 Console Python

>>> tableau1 = [0, 1, 0, 1, 0, 1, 0]
>>> separe(tableau1)
>>> tableau1
[0, 0, 0, 0, 1, 1, 1]

🐍 Console Python

>>> tableau2 = [1, 1, 1, 0, 0, 0]
>>> separe(tableau2)
>>> tableau2
[0, 0, 0, 1, 1, 1]

∞/∞

def separe(zerospy-undetpy-unduns):bksl-nl """place tous les 0 de zerospy-undetpy-unduns à gauche et tous les 1 à droite"""bksl-nl debut = ... # indice de débutbksl-nl fin = ... # indice de finbksl-nl while debut < fin:bksl-nl if zerospy-undetpy-unduns[debut] == 0:bksl-nl debut = ...bksl-nl else:bksl-nl zerospy-undetpy-unduns[debut] = ...bksl-nl ... = 1bksl-nl fin = ...bksl-nlbksl-nl# testsbksl-nlbksl-nltableau1 = [0, 1, 0, 1, 0, 1, 0]bksl-nlsepare(tableau1)bksl-nlassert tableau1 == [0, 0, 0, 0, 1, 1, 1]bksl-nlbksl-nltableau2 = [1, 1, 1, 0, 0, 0]bksl-nlsepare(tableau2)bksl-nlassert tableau2 == [0, 0, 0, 1, 1, 1]bksl-nlbksl-nldef separe(zerospy-undetpy-unduns):bksl-nl """place tous les 0 de zerospy-undetpy-unduns à gauche et tous les 1 à droite"""bksl-nl debut = 0 # indice de débutbksl-nl fin = len(zerospy-undetpy-unduns) - 1 # indice de finbksl-nl while debut < fin:bksl-nl if zerospy-undetpy-unduns[debut] == 0:bksl-nl debut = debut + 1bksl-nl else:bksl-nl zerospy-undetpy-unduns[debut] = zerospy-undetpy-unduns[fin]bksl-nl zerospy-undetpy-unduns[fin] = 1bksl-nl fin = fin - 1bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nltableau1 = [0, 1, 0, 1, 0, 1, 0]bksl-nlsepare(tableau1)bksl-nlassert tableau1 == [0, 0, 0, 0, 1, 1, 1]bksl-nlbksl-nltableau2 = [1, 1, 1, 0, 0, 0]bksl-nlsepare(tableau2)bksl-nlassert tableau2 == [0, 0, 0, 1, 1, 1]bksl-nlbksl-nl

Commentaires⚓︎

Pas la peine d'échanger⚓︎

Normalement pour échanger 2 valeurs dans un tableau, il faut faire 3 affectations (ou une affectation double a, b = b, a).

Dans notre cas, puisqu'on sait que le tableau ne contient que des 0 ou des 1, dans le else on sait qu'il s'agit d'un 1. On peut doc se passer de l'échange et faire uniquement deux affectations :

🐍 Script Python

        ...
        else:
            zeros_et_uns[debut] = zeros_et_uns[fin]
            zeros_et_uns[fin] = 1
        ...

au lieu de :

🐍 Script Python

        ...
        else:
            valeur = zeros_et_uns[debut]
            zeros_et_uns[debut] = zeros_et_uns[fin]
            zeros_et_uns[fin] = valeur
        ...

Compter⚓︎

On peut compter les 0 et écrire le bon nombre de 0 et de 1 après.