Formation I.S.N.

Pancake sorting

Illustration.

Ci-dessous, on dispose d'une pile de crêpes. Il s'agit de les ranger dans l'ordre croissant, la crêpe de diamètre le plus faible en haut.

Vous n'avez le droit qu'à une seule opération : glisser une spatule sous une crêpe et retourner toute la pile de crêpes se trouvant ainsi sur votre spatule. On obtient ici cet effet en cliquant sur la crêpe la plus basse dans la pile à retourner.

Faîtes quelques essais et essayez de déterminer un algorithme de tri.

formulation d'un algorithme.

Formulez, en français, un algorithme de tri du tas de crêpe respectant les contraintes imposées.

  • une formulation

On note n le nombre de crêpes total.

Pour k allant de n à 2 (par pas de -1) :
  repérer la crêpe la plus grande dans les k crêpes du sommet;
  retourner tout le sommet à partir de cette plus grande crêpe;
  retourner les k crêpes du sommet.