Tassement

Problème à résoudre

Soit le tableau (collection) t de longueur n contenant des valeurs entières quelconques. L’objectif de cet exercice est de tasser toutes les valeurs non nulles au début du tableau (à partir de l’indice 0) et de regrouper les valeurs nulles à la fin du tableau. L’ordre des valeurs après tassement n’est pas conservé.

 

Démonstration

  • tableau avant : t=[3, 0, 0, 1, 3, 5, 3, 0, 4]
  • tableau après : t=[3, 4, 3, 1, 3, 5, 0, 0, 0]

Fonctionnement manuel

  • La première valeur est non nulle, on passe à la valeur suivante
  • La seconde valeur vaut 0, échange avec la dernière
  • Le nouvel indice de la dernière valeur candidate à l’échange est à la position 7 (valeur 0).
  • etc.

    Enregistrement de la boucle

    • A la rencontre, d’une valeur non nulle, avancer à la suivante
    • A la rencontre d’un zéro, il est échangé avec une valeur de la fin du tableau (valeur candidate). 

    Sortie de la boucle

    • Il n’y a plus aucune valeur à traiter

    Démarrage

    • La première valeur candidate est à la fin
    • Parcourir la tableau à partir de l’indice 0.

    Terminaison

    • Afficher le nombre de valeurs tassées (les valeurs non nulles)

    Exécution complète

    Programme AlgoTouch

    Define tasser
    From
      i = 0 ;
      j = t.length – 1 ;
    // …
    Until
      (i > j)
    // …
    Loop
      if (t[i] != 0) {
        i = i + 1 ;
      }
      else {
        // t[i] == 0
        tmp = t[i];
        t[i] = t[j] ;
        t[j] = tmp;
        j = j – 1 ;
      }
    // …
    Terminate
      Write “Valeurs tassées : ” i ;
    // …
    End

    Programme Python

    t = [0, 5, 0, 4, 0, 0, 7, 2]n = len(t)

    i = 0
    j = len(t)-1
    while (i != j):
      if (t[i] != 0):
        i = i + 1
      else :
        tmp = t[i]    t[i] = t[j]    t[j] = tmp
        j = j – 1