Trier une liste de nombres (tutoriel)

Trier une liste de nombres

Ce tutoriel explique comment trier une liste de nombres.

Trier une liste

En informatique, trier une liste de nombre est une méthode nécessaire et généralement incorporée par défaut aux différents langages de programmation. Le langage Scratch ne contient pas de bloc Scratch permettant de trier une liste.

Voici quelques exemples d'utilisation d'une liste triée :

réaliser des algorithmes de recherche plus performants, comme la dichotomie ;
sélectionner des éléments par différence ou seuil ;
réaliser des classements, afficher des scores de manière plus lisible ou encore réaliser un podium ;

Différents algorithmes de tri (cliquer pour agrandir).

Il existe divers algorithmes de tri. Certains sont plus efficaces que d'autres, tandis que les moins efficaces sont généralement beaucoup plus compréhensibles. Un algorithme de tri peut être défini comme efficace en fonction de ses complexités algorithmiques (le nombre moyen d'opérations réalisées) et mémorielles (l'utilisation de la mémoire de l'appareil).

Les algorithmes de tri présentés sur cette page fonctionnement par comparaison.

Algorithmes

Ce tutoriel vous propose 4 différents algorithmes de tri.

Info :

Le code proposé ci-dessous peut-être consulté en action et récupéré sur ce projet.

Info :

Les algorithmes proposés trient par ordre croissant. Il est possible de trier par ordre décroissant en inversant le sens de la condition logique comparant les valeurs des algorithmes.

LeSaviezVous :

Utiliser

last

(en copiant-collant) dans une entrée de liste attendant un indice correspond au dernier élément de liste.

Comparaison des algorithmes

La table suivante compare les divers algorithmes présentés sur cette page.

La complexité en temps des algorithmes (ou complexité algorithmique) est une grandeur servant à mesurer l'efficacité d'exécution d'un algorithme, tandis que la complexité en espace (ou complexité mémorielle) permet de mesurer l'utilisation de la mémoire par un algorithme.

Graphique représentant les principales complexités algorithmiques :

,

n log n

et

n^(2)

.

Tableau comparatif des tris par comparaisons
Nom	Complexité algorithmique			Complexité mémorielle
Nom	Meilleur cas	Cas moyen	Pire cas	Complexité mémorielle
Tri à bulles	`n`	`n²`	`n²`	`1`
Tri par insertion	`n`	`n²`	`n²`	`1`
Tri rapide	`n log n`	`n log n`	`n²(cas rare)`	`n (pire cas)`
Tri fusion	`n log n`	`n log n`	`n log n`	`n (pire cas)`

Info :

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

Permuter des éléments

Le bloc suivant est nécessaire à plusieurs des algorithmes de tri présentés sur cette page. Il permet d'échanger la valeur de deux éléments dans une liste.

définir Liste / Permuter \[i, j] (i) (j)
mettre [var v] à (élément (i) de [liste v]) // sauvegarde de la valeur en i
remplacer l'élément (i) de la liste [liste v] par (élément (j) de [liste v]) // on écrase l'élément i
remplacer l'élément (j) de la liste [liste v] par (var) // on écrase l'élément j avec la valeur en mémoire

Bulles

Le tri à bulles consiste à comparer un élément à l'indice i sur tous les indices de la liste suivant, et à déplacer à cet index i l'élément le plus petit observé, qui remonte alors comme une « bulle sous l'eau ».

définir Tri à Bulles
mettre [index v] à [1] // l'indice de l'élément à comparer
mettre [max v] à [1] // indice maximum atteint
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)
Liste / Permuter \[i, j] (index) ((index) + (1)) :: custom
si <(index::variables) > [1]> alors
ajouter (-1) à [index v] // on retourne à l'élément précédent
fin
sinon
si <(index) < (max)> alors
mettre [index v] à (max) // on retourne à l'indice maximum
sinon
ajouter (1) à [index v] // on passe à l'élément suivant
fin
fin
si <(index) > (max)> alors
mettre [max v] à (index) // on sauvegarde l'indice maximum
fin
fin

Insertion

Le tri par insertion consiste à remonter l'élément d'indice i jusqu'à sa bonne position.

définir Tri par Insertion
mettre [index i v] à [2] // indice initial
répéter jusqu'à ce que <(longueur de [liste v]) < (index i)>
mettre [index j v] à ((index i) - [1]) // indice de recherche
répéter jusqu'à ce que <<(élément (index j) de [liste v]) < (élément (index i) de [liste v])> ou <(index j) < [1]>> // on remonte jusqu'à la bonne position
ajouter [-1] à [index j v]
fin
insérer (élément (index i) de [liste v]) en position ((index j) + [1]) de [liste v]
supprimer l'élément ((index i) + [1]) de [liste v] // et on insère l'élément
ajouter [1] à [index j v]
fin

Rapide

Le tri rapide (ou « tri pivot », de l'anglais "Quick Sort") consiste à placer des pivots dans la liste et à trier respectivement à droite et à gauche de ce pivot en utilisant le principe « diviser pour régner ».

définir Tri Rapide
si <(longueur de [liste v]) < (2)> alors
stop [ce script v]
fin
supprimer tous les éléments de la liste [pivot / gauche v]
supprimer tous les éléments de la liste [pivot / droite v]
ajouter [1] à [pivot / gauche v] :: list
ajouter (longueur de [liste v]) à [pivot / droite v] :: list
répéter jusqu'à ce que <(élément [last] de [pivot / gauche v]) > (élément [last] de [pivot / droite v])>
mettre [pivot / gauche v] à (élément [last] de [pivot / gauche v])
mettre [pivot / droite v] à (élément [last] de [pivot / droite v])
supprimer l'élément [last] de [pivot / gauche v]
supprimer l'élément [last] de [pivot / droite v]
si <(pivot / gauche :: variables) < (pivot / droite :: variables)> alors
mettre [pivot / valeur v] à (élément (pivot / droite :: variables) de [liste v])
mettre [pivot / i v] à (pivot / gauche :: variables)
mettre [pivot / j v] à (pivot / gauche :: variables)
répéter ((pivot / droite :: variables) - (pivot / gauche :: variables)) fois
si <non <(élément (pivot / i) de [liste v]) > (pivot / valeur)>> alors // utiliser « < » pour basculer en ordre décroissant
Liste / Permuter \[i, j] (pivot / i) (pivot / j) :: custom
ajouter [1] à [pivot / j v]
fin
ajouter [1] à [pivot / i v]
fin
Liste / Permuter \[i, j] (pivot / droite :: variables) (pivot / j) :: custom
ajouter (pivot / gauche :: variables) à [pivot / gauche v] :: list
ajouter (pivot / j) à [pivot / gauche v] :: list
ajouter ((pivot / j) - [1]) à [pivot / droite v] :: list
ajouter (pivot / droite :: variables) à [pivot / droite v] :: list
fin
fin

Fusion

Le tri fusion (de l'anglais "Merge Sort") consiste à diviser la liste par 2 jusqu'à trier des paires de celles, puis de faire fusionner les paires triées en utilisant le principe « diviser pour régner ».

définir Tri Fusion \[début, fin] (début) (fin)
si <(début) = (fin)> alors
    stop [ce script v] // une liste de 1 élément est toujours triée
fin
Tri Fusion \[début, fin] (début) ((arrondi de (((début) + (fin)) / (2))) - (1))
Tri Fusion \[début, fin] (arrondi de (((début) + (fin)) / (2))) (fin)
mettre [index i v] à (début)
mettre [index j v] à (arrondi de (((début) + (fin)) / (2)))
répéter jusqu'à ce que <<(index i) = (fin)> ou <(index j) > (fin)>> // on fusionne les listes triées
    si <(élément (index j) de [liste v]) < (élément (index i) de [liste v])> alors
        insérer (élément (index j) de [liste v]) en position (index i) de [liste v]
        ajouter [1] à [index j v]
        supprimer l'élément (index j) de [liste v]
        ajouter [1] à [index i v]
    sinon
        ajouter [1] à [index i v]
    fin
fin

LeSaviezVous :

Ce bloc personnalisé est « récursif », il s'exécute lui-même en modifiant les paramètres de son exécution.