De Scratch Wiki en français


Trier une liste de nombres


Ce tutoriel explique comment trier une liste de nombres.

Utilisation

Trier une liste de nombres peur être utile dans plusieurs cas :

Elle vous permet par exemple d'établir un classement (entre plusieurs joueurs par exemple) afin d'établir un podium ou juste d'afficher des scores de manière lisible, rangés par ordre décroissant.

Différents algorithmes de classement (cliquer pour agrandir)

Différents algorithmes de tri

Il existe plusieurs façons (algorithmes) de trier une liste, certaines étant plus efficaces que d'autres. L'efficacité dépend de

  • la longueur de la liste à trier
  • l'arrangement des éléments dans la liste à trier (aléatoire, presque trié, inversé, etc...)

Le but étant de minimiser le nombre d'opérations nécessaires pour trier la liste (lecture d'éléments de la liste, comparaison de nombres, échange de place des valeurs, etc) et donc le temps nécessaire pour trier la liste.

Info
 Info :
Tous les scripts ci-dessous trient les nombre par ordre croissant.

Bubble Sort (Tri à bulles, ou tri par propagation)

Le tri à bulles consiste à comparer répétitivement les éléments consécutifs de la liste, et à les permuter (échanger de place) lorsqu'ils sont mal triés.

quand le drapeau vert pressé
mettre [index v] à [1] // l"index de l'élément à comparer
répéter jusqu'à ce que <(index::variables) = (longueur de [liste v] :: list)> // tant qu'on a pas atteint le bout de la liste
si <((élément (index::variables) de [liste v] :: list) - (élément ((index::variables) + (1)) de [liste v] :: list)) > [0]> alors // si l’élément à l'index est plus grand que le suivant (ordre croissant)
mettre [échange v] à (élément (index::variables) de [liste v] :: list) // variable temporaire pour l'échange
remplacer l'élément (index::variables) de la liste [liste v] par (élément ((index::variables) + (1)) de [liste v] :: list) // on échange les valeurs
remplacer l'élément ((index::variables) + (1)) de la liste [liste v] par (échange) // on échange les valeurs
ajouter (-1) à [index v] // on compare avec l'élément précédent
si <(index::variables) < [1]> alors
mettre [index v] à [1]
fin
sinon
ajouter (1) à [index v] // on passe à l'élément suivant
fin
fin

Variantes

  • Plus petit

<((élément (index::variables) de [liste v] :: list) - (élément ((index::variables) + (1)) de [liste v] :: list)) < [0]>

  • Plus grand ou égal

<non <((élément (index::variables) de [liste v] :: list) - (élément ((index::variables) + (1)) de [liste v] :: list)) < [0]>>

  • Plus petit ou égal

<non <((élément (index::variables) de [liste v] :: list) - (élément ((index::variables) + (1)) de [liste v] :: list)) > [0]>>


Insertion

Le tri par insertion consiste à insérer chaque élément au bon endroit dans une nouvelle liste.

quand le drapeau vert pressé
répéter jusqu'à ce que <(longueur de [liste v]) = [0]>
mettre [index v] à (1)
répéter jusqu'à ce que <<(élément (index) de [triés v]) > (élément (1 v) de [liste v])> ou <(élément (index) de [triés v]) = []>>
ajouter (1) à [index v]
fin
insérer (élément (1) de [liste v]) en position (index) de [triés v]
supprimer l'élément (1) de [liste v]
fin

Il n'est cependant pas possible de trier la liste dans un autre sens avec cette méthode.


Cet article fait partie de la catégorie des tutos
Tous les articles de cette catégorie :