Source: Scratch Wiki en français
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 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 :
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 que l'on n'a pas atteint la fin de la liste si <(élément (index::variables) de [liste v] :: list) > (élément ((index::variables) + (1)) de [liste v] :: list)> 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 si <(index::variables) > [1]> alors ajouter (-1) à [index v] // on retourne à l'élément précédent fin sinon ajouter (1) à [index v] // on passe à l'élément suivant fin fin
Variante
- Plus petit (décroissant)
<(élément (index::variables) de [liste v] :: list) < (élément ((index::variables) + (1)) de [liste v] :: list)>
Insertion
Le tri par insertion consiste à insérer chaque élément au bon endroit dans une nouvelle liste.
Supposons une liste « liste » à trier et « triés » vide.
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] de [liste v])> ou <(index) > (longueur 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
En utilisant la même méthode que celle donnée plus haut, il est possible de trier en sens inverse la liste.
