Formation I.S.N.

Bubble sort

tri par remontée de bulles.

Ci-dessous, des bulles dans une bouteille. Il s'agit de les ranger dans l'ordre croissant, la bulle de diamètre le plus faible en haut.

Vous n'avez le droit qu'à un seul type d'opération : échanger deux bulles consécutives lorsque la bulle la plus basse est la plus légère (la plus petite). Cet échange sera réalisé en cliquant sur la bulle basse.

Testez, rangez, concevez un algorithme...

formulation d'un algorithme.

Formulez, en français, un algorithme de tri des bulles en utilisant la seule opération vue ci-dessus.

  • le principe du bubble sort
  • une formulation

Nous exposons ici le principe classique nommé "bubble sort".

On numérote 1, 2, ..., n les positions possibles des bulles (de haut en bas).

  1. On part du bas de la bouteille. On clique les bulles de rangs n, n-1, n-2, n-3, ..., 2. On a ainsi remonté la plus petite bulle à sa position définitive.
  2. Il suffit de recommencer le même procédé sur la sous-liste des bulles de rangs 2, 3, ..., n, puis sur la sous-liste des bulles de rangs 3, 4, ..., n. Et ainsi de suite.

On numérote 1, 2, ..., n les rangs des bulles.

Pour i allant de 1 à n-1 :
  pour j allant de n à i+1 (par pas de -1) :
    si bulle de rang j est plus légère que bulle de rang j-1 :
      échanger les positions de ces deux bulles