Le jeu dans la main

Dans les pages qui suivent, on va essayer à nouveau de trier la liste suivant le principe d'insertion, mais cette fois sans créer une nouvelle liste: on ne s'autorisera que des déplacements d'éléments à l'intérieur de la liste donnée en paramètre.

On commence, dans cette page, par une analogie avec un joueur de cartes: au lieu de prendre les cartes une par une dans le tas, il reçoit toutes ses cartes d'un coup dans la main et doit les trier en les gardant dans cette main.

Un exemple

Notre joueur prend immédiatement toutes les cartes en main et les trie dans sa main.

En d'autres termes, on ne dispose plus d'un tas et d'une main mais seulement de la main. D'un point de vue informatique, on s'interdit de créer une liste intermédiaire: on doit trier avec une liste unique.

Illustration avec main = [4,2,7,1,8,5,3].

• main = [4,2,7,1,8,5,3].
• la carte d'indice 1 est mise à sa place dans main[0..1]: main = [2,4,7,1,8,5,3].
• la carte d'indice 2 est mise à sa place dans main[0..2]: main = [2,4,7,1,8,5,3].
• la carte d'indice 3 est mise à sa place dans main[0..3]: main = [1,2,4,7,8,5,3].
• la carte d'indice 4 est mise à sa place dans main[0..4]: main = [1,2,4,7,8,5,3].
• la carte d'indice 5 est mise à sa place dans main[0..5]: main = [1,2,4,5,7,8,3].
• la carte d'indice 6 est mise à sa place dans main[0..6]: main = [1,2,3,4,5,7,8].

Important

D'un point de vue informatique, l'intérêt de cette contrainte (non création d'une liste intermédiaire) est d'économiser de la place en mémoire: au lieu de disposer de deux listes de taille n, on dispose à tout moment d'une seule liste de taille n. Pour des grandes valeurs de n, ce gain peut être important, voire indispensable.

Exercice

Illustrer de même le tri du joueur de cartes avec la main initiale main = [8, 1, 7, 2, 4, 3, 1, 6].

Réponse

• main = [8, 1, 7, 2, 4, 3, 1, 6].
• Rangement de la carte d'indice 1 dans main[0..1] : main = [1, 8, 7, 2, 4, 3, 1, 6].
• Rangement de la carte d'indice 2 dans main[0..2] : main = [1, 7, 8, 2, 4, 3, 1, 6].
• Rangement de la carte d'indice 3 dans main[0..3] : main = [1, 2, 7, 8, 4, 3, 1, 6].
• Rangement de la carte d'indice 4 dans main[0..4] : main = [1, 2, 4, 7, 8, 3, 1, 6].
• Rangement de la carte d'indice 5 dans main[0..5] : main = [1, 2, 3, 4, 7, 8, 1, 6].
• Rangement de la carte d'indice 6 dans main[0..6] : main = [1, 1, 2, 3, 4, 7, 8, 6].
• Rangement de la carte d'indice 7 dans main[0..7] : main = [1, 1, 2, 3, 4, 6, 7, 8].