De Scratch Wiki en Français

m (Insertion)
m (Bubble Sort (Tri à bulles, ou tri par propagation))
 
Ligne 28 : Ligne 28 :
 
quand le drapeau vert pressé
 
quand le drapeau vert pressé
 
mettre [index v] à [1] // l"index de l'élément à comparer
 
mettre [index v] à [1] // l"index de l'élément à comparer
répéter jusqu'à ce que <(index) = (longueur de [liste v] :: list)> // tant qu'on a pas atteint le bout de la liste
+
répéter jusqu'à <(index) = (longueur de [liste v] :: list)> // tant qu'on a pas atteint le bout de la liste
 
si <((élément (index) de [liste v] :: list) - (élément ((index) + (1)) de [liste v] :: list)) > [0]> alors // si l’élément à l'index est plus grand que le suivant (ordre croissant)
 
si <((élément (index) de [liste v] :: list) - (élément ((index) + (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) de [liste v] :: list) // variable temporaire pour l'échange
 
mettre [échange v] à (élément (index) de [liste v] :: list) // variable temporaire pour l'échange

Version actuelle datée du 29 août 2019 à 02:24


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'à <(index) = (longueur de [liste v] :: list)> // tant qu'on a pas atteint le bout de la liste
si <((élément (index) de [liste v] :: list) - (élément ((index) + (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) de [liste v] :: list) // variable temporaire pour l'échange
remplacer l'élément (index) de la liste [liste v] par (élément ((index) + (1)) de [liste v] :: list) // on échange les valeurs
remplacer l'élément ((index) + (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) < [1]> alors
mettre [index v] à [1]
fin
sinon
ajouter (1) à [index v] // on passe à l'élément suivant
fin
fin


Aller sur la page du projet Voir à l'intérieur Remixer

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’à <(longueur de [lsite v] :: list) = [0]>
mettre [index v] à [0]
répéter jusqu’à <<(élément (index) de [triés v] :: list) > (élément (1 v) de [liste v] :: list)> ou <(élément (index) de [triés v] :: list) = []>>
ajouter à [index v] (1)
end
insérer (élément (1 v) de [liste v] :: list) en position (1 v) de la liste [list v]
supprimer l'élément (1 v) de la liste [liste v]
end


Aller sur la page du projet Voir à l'intérieur Remixer


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