Tri d'un tableau de 0 et de 1

On considère un tableau d'entiers dont la valeur peut être soit 0 soit 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
           │              │
           ▼              ▼
┌─────────┬────────────────┬─────────┐
│ 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.

La fonction separe prend en paramètre un tableau zeros_et_uns dont les éléments sont des 0 et 1 et renvoie le tableau trié en procédant comme décrit ci-dessus.

Exemples

🐍 Console Python

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

🐍 Console Python

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

Attention

Dans cet exercice, il est interdit d'utiliser sort ou sorted

Compléter la fonction separe.

###

Lancer # testsbksl-nlbksl-nltabpy-und1 = [0, 1, 0, 1, 0, 1, 0]bksl-nlsepare(tabpy-und1)bksl-nlassert tabpy-und1 == [0, 0, 0, 0, 1, 1, 1]bksl-nlbksl-nltabpy-und2 = [1, 1, 1, 0, 0, 0]bksl-nlsepare(tabpy-und2)bksl-nlassert tabpy-und2 == [0, 0, 0, 1, 1, 1]bksl-nlbksl-nl# autres testsbksl-nlbksl-nltableaupy-undvide = []bksl-nlsepare(tableaupy-undvide)bksl-nlassert tableaupy-undvide == []bksl-nlbksl-nlquepy-und0 = [0] py-str 100bksl-nlsepare(quepy-und0)bksl-nlassert quepy-und0 == [0] py-str 100bksl-nlbksl-nlquepy-und1 = [1] py-str 100bksl-nlsepare(quepy-und1)bksl-nlassert quepy-und1 == [1] py-str 100bksl-nlbksl-nlmonopy-und0 = [0]bksl-nlsepare(monopy-und0)bksl-nlassert monopy-und0 == [0]bksl-nlbksl-nlmonopy-und1 = [1]bksl-nlsepare(monopy-und1)bksl-nlassert monopy-und1 == [1]bksl-nlbksl-nlduo = [1, 0]bksl-nlsepare(duo)bksl-nlassert duo == [0, 1]bksl-nlbksl-nlunpy-undseulpy-und1py-unda = [1, 0, 0, 0, 0, 0]bksl-nlsepare(unpy-undseulpy-und1py-unda)bksl-nlassert unpy-undseulpy-und1py-unda == [0, 0, 0, 0, 0, 1]bksl-nlbksl-nlunpy-undseulpy-und1py-undb = [0, 0, 1, 0, 0, 0]bksl-nlsepare(unpy-undseulpy-und1py-undb)bksl-nlassert unpy-undseulpy-und1py-undb == [0, 0, 0, 0, 0, 1]bksl-nlbksl-nlunpy-undseulpy-und1py-undc = [0, 0, 0, 0, 0, 1]bksl-nlsepare(unpy-undseulpy-und1py-undc)bksl-nlassert unpy-undseulpy-und1py-undc == [0, 0, 0, 0, 0, 1]bksl-nlbksl-nlunpy-undseulpy-und0py-unda = [0, 1, 1, 1, 1, 1]bksl-nlsepare(unpy-undseulpy-und0py-unda)bksl-nlassert unpy-undseulpy-und0py-unda == [0, 1, 1, 1, 1, 1]bksl-nlbksl-nlunpy-undseulpy-und0py-undc = [1, 1, 1, 1, 1, 0]bksl-nlsepare(unpy-undseulpy-und0py-undc)bksl-nlassert unpy-undseulpy-und0py-undc == [0, 1, 1, 1, 1, 1]bksl-nlbksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder

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-nltabpy-und1 = [0, 1, 0, 1, 0, 1, 0]bksl-nlsepare(tabpy-und1)bksl-nlassert tabpy-und1 == [0, 0, 0, 0, 1, 1, 1]bksl-nlbksl-nltabpy-und2 = [1, 1, 1, 0, 0, 0]bksl-nlsepare(tabpy-und2)bksl-nlassert tabpy-und2 == [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-nl

A

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 donc 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. Par contre, cela nécessite de faire 2 parcours du tableau. Le premier pour compter les 0 et le deuxième pour modifier les valeurs.

Z