Algorithmes tri > Quadratiques

Algorithmes tri > Dichotomique

Algorithmes tri > Linéaires

Références

L'actualité

Parcours & Expérience





Librairie

L'information

Algorithmes de tri > Quadratiques > Tri à bulles (Bubble sort)

Le tri à bulles ou tri par propagation est un algorithme de tri qui consiste à faire remonter progressivement les plus grands éléments d'un tableau, comme les bulles d'air remontent à la surface d'un liquide.

								
Algorithme Tri_a_Bulles
	local: i , j , n, temp ∈ Entiers naturels
	Entrée - Sortie : Tab ∈ Tableau d'Entiers naturels de 1 a n éléments
	début
		//recommence une sous-suite (a1, a2, ... , ai)
		pour i de n jusquà 1 faire
			//échange des couples non classés de la sous-suite
			pour j de 2 jusquà i faire
				// aj-1et aj non ordonnés
				si Tab[ j-1 ] > Tab[ j ] alors
					temp ← Tab[ j-1 ] ;
					Tab[ j-1 ] ← Tab[ j ] ;
					//on échange les positions de aj-1et aj
					Tab[ j ] ← temp 
				Fsi
			fpour
		fpour
	Fin Tri_a_Bulles
Tableau initial (n°1 au n°19) :
3, 8, 7, 5, 2, 1, 9, 6, 4
Tableau une fois trié (n°1 au n°19) :
1, 2, 3, 4, 5, 6, 7, 8, 9
Autre version depuis l'indice zéro :
Tableau initial (n°0 au n°19) :
3, 8, 7, 5, 2, 1, 9, 6, 4, 0
Tableau une fois trié (n°0 au n°19) :
0, 1, 2, 3, 4, 5, 6, 7, 8, 9



Algorithmes de tri > Quadratiques > Tri de Shell (Shell sort)

Le tri de Shell ou Shell sort en anglais est un algorithme de tri. C'est une amélioration notable du tri par insertion au niveau de la vitesse d'exécution mais ce tri n'est pas stable. Le principe de l'algorithme est simple mais l'étude du temps d'exécution est très complexe, et plusieurs problèmes sont toujours ouverts à ce sujet.

Le nom vient de son inventeur Donald Shell (en) (1924-2015) qui publia l'algorithme dans le numéro de juillet 1959 de Communications of the ACM.

Tableau initial (n°1 au n°14) :
1 , 5 , 3 , 6 , 10 , 55 , 9 , 2 , 87 , 12 , 34 , 75 , 33 , 47
Tableau une fois trié (n°1 au n°14) :
1 , 2 , 3 , 5 , 6 , 9 , 10 , 12 , 33 , 34 , 47 , 55 , 75 , 87



Algorithmes de tri > Quadratiques > Tri par insertion (Insertion sort)

En informatique, le tri par insertion est un algorithme de tri classique. La plupart des personnes l'utilisent naturellement pour trier des cartes à jouer.

En général, le tri par insertion est beaucoup plus lent que d'autres algorithmes comme le tri rapide (ou quicksort) et le tri fusion pour traiter de grandes séquences, car sa complexité asymptotique est quadratique.

Le tri par insertion est cependant considéré comme le tri le plus efficace sur des entrées de petite taille. Il est aussi très rapide lorsque les données sont déjà presque triées. Pour ces raisons, il est utilisé en pratique en combinaison avec d'autres méthodes comme le tri rapide.

En programmation informatique, on applique le plus souvent ce tri à des tableaux. La description et l'étude de l'algorithme qui suivent se restreignent à cette version, tandis que l'adaptation à des listes est considérée plus loin. 

								
Algorithme Tri_Insertion
	local: i , j , n, v ∈ Entiers naturels
	Entrée : Tab ∈ Tableau d'Entiers naturels de 0 à n éléments
	Sortie : Tab ∈ Tableau d'Entiers naturels de 0 à n éléments (le même tableau)
	
	{
	dans la cellule de rang 0 se trouve une sentinelle 
	chargée d'éviter de tester dans la boucle tantque... 
	faire si l'indice j n'est pas inférieur à 1, 
	elle aura une valeur inférieure à toute valeur 
	possible de la liste
	}

début
	pour i de 2 jusquà n faire //la partie non encore triée (ai, ai+1, ... , an)
		v ← Tab[ i ] ; // l'élément frontière : ai
		j ← i ; // le rang de l'élément frontière
		//on travaille sur la partie déjà triée (a1, a2, ... , ai)
		Tantque Tab[ j-1 ]> v faire 
			Tab[ j ] ← Tab[ j-1 ]; // on décale l'élément
				j ← j-1; // on passe au rang précédent
			FinTant ;
			Tab[ j ] ← v //on recopie ai dans la place libérée
	fpour
Fin Tri_Insertion
Tableau initial :
25 , 7 , 14 , 26 , 25 , 53 , 74 , 99 , 24 , 98 , 89
Tableau une fois trié :
7 , 14 , 24 , 25 , 25 , 26 , 53 , 74 , 89 , 98 , 99



Algorithmes de tri > Quadratiques > Tri par sélection (Selection sort)

Le tri par sélection (ou tri par extraction) est un algorithme de tri par comparaison. Cet algorithme est simple, mais considéré comme inefficace, car il s'exécute en temps quadratique en le nombre d'éléments à trier, et non en temps pseudo linéaire.

								
  procédure tri_selection(tableau t, entier n)
      pour i de 1 à n - 1
          min ← i
          pour j de i + 1 à n
              si t[j] < t[min], alors min ← j
          fin pour
          si min ≠ i, alors échanger t[i] et t[min]
      fin pour
  fin procédure
Tableau initial (n°1 au n°10) :
100 , 50 , 20 , 40 , 10 , 60 , 80 , 70 , 90 , 30
Tableau une fois trié (n°1 au n°10) :
10 , 20 , 30 , 40 , 50 , 60 , 70 , 80 , 90 , 100



Algorithmes de tri > Dichotomique > Tri fusion (Merge sort)

Cette implémentation effectue une fusion vers un tableau temporaire puis recopie les données fusionnées dans le tableau principal.

Tableau initial (n°1 au n°10) :
3, 8, 7, 5, 2, 1, 9, 6, 4
Tableau une fois trié (n°1 au n°10) :
1, 2, 3, 4, 5, 6, 7, 8, 9



Algorithmes de tri > Dichotomique > Smoothsort

Smoothsort est un algorithme de tri par comparaison inventé en 1981 par Edsger Dijkstra.

La transition entre les temps d'exécution entre les listes déjà triées et les listes mélangées ou à l'envers est progressive d'où le nom smoothsort, smooth signifiant doux, lisse. C'est un tri sur place, c'est-à-dire qu'il n'y a pas de zone mémoire allouée supplémentaire pour stocker les éléments.

Si l'algorithme smoothsort est plus rapide que le tri par tas pour des listes peu mélangées, il est légèrement plus lent que le tri par tas pour des listes qui sont plutôt dans le sens décroissant au départ. En effet, les données de départ sont alors plus proche de la structure de tas.



Algorithmes de tri > Dichotomique > Tri par tas (Heapsort)

En informatique, le tri par tas est un algorithme de tri par comparaisons. Cet algorithme est de complexité asymptotiquement optimale, c'est-à-dire que l'on démontre qu'aucun algorithme de tri par comparaison ne peut avoir de complexité asymptotiquement meilleure. Sa complexité est proportionnelle à n log n où n est la longueur du tableau à trier. Le tri par tas se fait en place, c'est-à-dire qu'il ne nécessite pas l'allocation d'une zone mémoire supplémentaire (plus précisément il ne nécessite qu'une allocation d'une zone mémoire de taille O(1)).



Algorithmes de tri > Dichotomique > Tri rapide (Quicksort)

Le tri rapide (en anglais quicksort) est un algorithme de tri inventé par C.A.R. Hoare en 19611 et fondé sur la méthode de conception diviser pour régner. Il est généralement utilisé sur des tableaux, mais peut aussi être adapté aux listes. Dans le cas des tableaux, c'est un tri en place mais non stable.

La complexité moyenne du tri rapide pour n éléments est proportionnelle à n log n, ce qui est optimal pour un tri par comparaison, mais la complexité dans le pire des cas est quadratique. Malgré ce désavantage théorique, c'est en pratique un des tris les plus rapides, et donc un des plus utilisés. Le cas le pire est en effet peu probable lorsque l'algorithme est correctement mis en oeuvre et il est possible de s'en prémunir définitivement avec la variante Introsort.

Le tri rapide ne peut cependant pas tirer avantage du fait que l'entrée est déjà presque triée. Dans ce cas particulier, il est plus avantageux d'utiliser le tri par insertion ou l'algorithme smoothsort.



Algorithmes de tri > Linéaires > Tri comptage (Tri casier, Counting sort)

Le tri comptage (appelé aussi tri casier, ou encore counting sort en anglais) est un algorithme de tri par dénombrement qui s'applique sur des valeurs entières.