Les Tris

Trier est une opération courante en informatique. Pour résoudre un problème on commence souvent par trier. Si L est une liste, la méthode pour trier une liste est

L.sort().

NB : la liste est triée sur place et ne renvoie aucune valeur (ne pas écrire L=L.sort() mais seulement  L.sort()).

Exemple d'application : Médiane d'une liste L de nombres

[Principe]

Il faut d'abord trier la liste L. La médiane correspond à la valeur qui sépare la série en 2.

n étant le nomber d'éléments de L, si n est impair, c'est L[(n+1)/2], si n est pair, c'est (L[n/2] +L[n/2+1])/2

[Programme]

Voici trois méthodes de Tri

Tri élémentaire

Principe

On recherche la plus grande valeur de L, on la retire et on la place dans une deuxième liste. Cette méthode élémentaire est de très mauvaise qualité et exige deux listes en mémoire.

Tri à bulles

[Principe]

Le tri à bulles ou tri par propagation est un algorithme de l'algorithme parcourt le tableau, compare les couples d'éléments successifs. Lorsque les deux éléments ne sont pas dans l'ordre croissant, ils sont échangés. Après chaque parcours complet du tableau, l'algorithme recommence l'opération.

Deux options sont possibles :

  • A chaque étape, on sait que le maximum est repoussé en fin de liste, donc on recommence en allant à chaque étape une case moins loin. Dans ces conditions, le nombre de parcours est n-1 où n est le nombre d'éléments de la liste.

[Fonction]

  •  Lorsqu'aucun échange n'a lieu pendant un parcours, cela signifie que le tableau est trié. On arrête alors l'algorithme.

[Fonction]

Tri par insertion

[Principe]

Dans l'algorithme, on parcourt le tableau à trier du début à la fin. Au moment où on considère le i-ème élément, les éléments qui le précèdent sont déjà triés.  

L'objectif d'une étape est alors d'insérer le i-ème élément à sa place parmi ceux qui précèdent.

Il faut pour cela  comparer T[i] avec les valeurs précédentes de T.

Si on trouve T[j] > T[i], on insère la valeur T[i] avant la valeur T[j] (pour cela,  on detruit T[i] et on insere en j-eme position la valeur x=T[i])

[Fonction]

 

Fichier Joint: 

Ajouter un commentaire

Plain text

  • Aucune balise HTML autorisée.
  • Les adresses de pages web et de courriels sont transformées en liens automatiquement.
  • Les lignes et les paragraphes vont à la ligne automatiquement.
CAPTCHA
This question is for testing whether or not you are a human visitor and to prevent automated spam submissions.
Image CAPTCHA
Saisir les caractères affichés dans l'image.