De 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 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.
