A voir également:
- Trier une liste par ordre croissant python sans sort
- Excel trier par ordre croissant chiffre - Guide
- Liste déroulante excel - Guide
- Citizen code python avis - Accueil - Outils
- Liste déroulante en cascade - Guide
- Liste code ascii - Guide
2 réponses
Bonjour,
Algorithmes de tri
1. Introduction
On considère une liste de N nombres x0,x1,x2...xN-1. Le tri est une opération de permutation de ces N nombres qui donne une liste de nombres rangés dans l'ordre croissant :
x'0≤x'1≤x'2⋯≤x'N-1(1)
2. Tri par insertion
2.a. Algorithme
Soit L la liste de nombres à trier. Le tri par insertion consiste à prendre les éléments de L un par un, dans l'ordre de rangement dans la liste, et à les insérer dans une liste L1 au bon emplacement.
Supposons que l'on ait déjà trié les n nombres d'indices i=0 à i=n-1 de L. Ces nombres se trouvent dans la liste L1 dans l'ordre croissant. Le nombre L[n] doit être inséré dans la liste L1 juste après le nombre de L1 le plus grand qui lui est inférieur ou égal, ou bien juste avant le nombre le plus petit qui lui est supérieur.
Pour éviter d'avoir à créer une seconde liste L1, il est commode de travailler entièrement sur la liste L : les n premiers nombres de L sont alors les nombres déjà triés (c.a.d. la liste L1). Voyons comment insérer le nombre L[n]. La figure suivante montre un exemple. La liste des nombres déjà triés est (1,3,5,6,9) et le nombre à insérer est 2.
Une manière efficace de le faire est de mémoriser le nombre à insérer L[n] puis de décaler vers la droite les nombres (par ordre d'indice décroissant) tant qu'ils sont supérieurs au nombre à insérer. Pour finir, le nombre à insérer est placé à l'emplacement du dernier nombre décalé.
Algorithmes de tri
1. Introduction
On considère une liste de N nombres x0,x1,x2...xN-1. Le tri est une opération de permutation de ces N nombres qui donne une liste de nombres rangés dans l'ordre croissant :
x'0≤x'1≤x'2⋯≤x'N-1(1)
2. Tri par insertion
2.a. Algorithme
Soit L la liste de nombres à trier. Le tri par insertion consiste à prendre les éléments de L un par un, dans l'ordre de rangement dans la liste, et à les insérer dans une liste L1 au bon emplacement.
Supposons que l'on ait déjà trié les n nombres d'indices i=0 à i=n-1 de L. Ces nombres se trouvent dans la liste L1 dans l'ordre croissant. Le nombre L[n] doit être inséré dans la liste L1 juste après le nombre de L1 le plus grand qui lui est inférieur ou égal, ou bien juste avant le nombre le plus petit qui lui est supérieur.
Pour éviter d'avoir à créer une seconde liste L1, il est commode de travailler entièrement sur la liste L : les n premiers nombres de L sont alors les nombres déjà triés (c.a.d. la liste L1). Voyons comment insérer le nombre L[n]. La figure suivante montre un exemple. La liste des nombres déjà triés est (1,3,5,6,9) et le nombre à insérer est 2.
Une manière efficace de le faire est de mémoriser le nombre à insérer L[n] puis de décaler vers la droite les nombres (par ordre d'indice décroissant) tant qu'ils sont supérieurs au nombre à insérer. Pour finir, le nombre à insérer est placé à l'emplacement du dernier nombre décalé.
Bonjour,
Il existe de nombreux algorithmes de tri (voir ce lien), donc il faudrait indiquer lequel tu souhaites implémenter.
Le tri par insertion (suggéré par jeepee) est sans doute l'un des plus simple à réaliser, mais pas le plus performant. Son pseudo code est reporté dans cette page.
Bonne chance
Il existe de nombreux algorithmes de tri (voir ce lien), donc il faudrait indiquer lequel tu souhaites implémenter.
Le tri par insertion (suggéré par jeepee) est sans doute l'un des plus simple à réaliser, mais pas le plus performant. Son pseudo code est reporté dans cette page.
Bonne chance