Utilisateur:Zetommyz/Revision tris

Tri à Bulles[modifier | modifier le code]

Le tri à bulles ou tri par propagation est un algorithme de tri qui consiste à faire remonter progressivement les plus petits éléments d'une liste, comme les bulles d'air remontent à la surface d'un liquide. L'algorithme parcourt la liste, et compare les couples d'éléments successifs. Lorsque deux éléments successifs ne sont pas dans l'ordre croissant, ils sont échangés. Après chaque parcours complet de la liste, l'algorithme recommence l'opération. Lorsqu'aucun échange n'a lieu pendant un parcours, cela signifie que la liste est triée : l'algorithme peut s'arrêter.

Cet algorithme est souvent enseigné en tant qu'exemple algorithmique. Cependant, il présente une complexité en О(n²) dans le pire des cas (où n est la longueur de la liste), ce qui le classe parmi les mauvais algorithmes de tri. Il n'est donc quasiment pas utilisé en pratique.

Complexité[modifier | modifier le code]

Pour un tableau de taille n, la boucle for sera exécutée n-1 fois et while sera exécutée une fois si permut == faux, c'est-à-dire le tableau est trié n-1 fois si permut est vrai.

Meilleur cas : O(n) le tableau est trié : n * 1 = o(n)
Pire cas: o(n²) le tableau est trié en ordre inverse (n -1)*(n-1) = o(n²)

Le nombre d'échanges de paires d'éléments successifs est égal au nombre de couples (i,j) tels que i < j et A(i) > A(j). Ce nombre d'échanges est indépendant de la manière d'organiser les échanges. Pour un tableau aléatoire, il est en moyenne égal à $N(N-1) \over 4$ .

Un dérivé du tri à bulles est le shakersort ou tri cocktail. Cette méthode de tri est basée sur une simple observation du comportement du tri à bulles : quand on fait un passage pour trier le maximum du tableau, on a tendance à déplacer les éléments les plus petits du tableau vers le début de celui-ci. Donc l'astuce consiste à alterner les sens de passage de notre bulle. Bien que le nombre d'échanges à effectuer soit identique (voir ci-dessus), on obtient un tri un peu plus rapide que la bulle. En effet, lors des changements de sens, cet algorithme relit les données les plus récentes et qui sont donc encore dans le tampon (cache) de la mémoire. Mais le temps d'exécution est toujours proportionnel à N² donc médiocre.

Exemple étape par étape[modifier | modifier le code]

Prenons la liste de chiffres suivante "5 1 4 2 8" et trions-la de manière croissante en utilisant l'algorithme de tri à bulles. Pour chaque étape, les élément comparés sont écrits en gras.

Première étape:
( 5 1 4 2 8 ) $\to$ ( 1 5 4 2 8 ) Ici, l'algorithme compare les deux premiers éléments (5 et 1) et les intervertit. (x)
( 1 5 4 2 8 ) $\to$ ( 1 4 5 2 8 )
( 1 4 5 2 8 ) $\to$ ( 1 4 2 5 8 )
( 1 4 2 5 8 ) $\to$ ( 1 4 2 5 8 ) Maintenant que ces deux éléments (5 et 8) sont triés (rangés), l'algorithme ne les intervertira plus.
Deuxième étape:
( 1 4 2 5 8 ) $\to$ ( 1 4 2 5 8 ) On recommence les mêmes opérations, voir $\to$ (x)
( 1 4 2 5 8 ) $\to$ ( 1 2 4 5 8 )
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
A ce stade, la liste est triée, mais l'algorithme ne sait pas si le travail (le tri) est terminé. L'algorithme doit effectuer un passage sans aucune interversion (échange) pour savoir si le travail est terminé.
Troisième étape:
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
Ici, la liste est triée et l'algorithme peut se terminer.

Implémentations[modifier | modifier le code]

Algorithme

maximum = longeur(tableau)
tant que maximum est supérieur à 0
    maximumTemporaire = 0
    pour i de 1 à maximum
        si la valeur à la position i-1 de tableau
           est supérieure à
           la valeur à la position i   de tableau:
              inverserLesValeursDesPositions(tableau, i, i-1)
              maximumTemporaire = i
    maximum = maximumTemporaire

Une mise en œuvre simple du tri à bulles sur un tableau d'entiers en C :

#define TRUE 1
#define FALSE 0

void tri_a_bulle(int t[], int const n) 
{
	int i   = 0; /* Indice de répétition du tri */
 	int j   = 0; /* Variable de boucle */
 	int tmp = 0; /* Variable de stockage temporaire */

	/* Booléen marquant l'arrêt du tri si le tableau est ordonné */
	int en_desordre = TRUE; 
	/* Boucle de répétition du tri et le test qui
	   arrête le tri dès que le tableau est ordonné */
	for(i = 0 ; (i < n) && en_desordre; i++)
	{
		/* Supposons le tableau ordonné */
		en_desordre = FALSE;
		/* Vérification des éléments des places j et j-1 */
		for(j = 1 ; j < n- i ; j++)
		{
			/* Si les 2 éléments sont mal triés */
			if(t[j] < t[j-1])
			{
				/* Inversion des 2 éléments */
 				tmp = t[j-1];
 				t[j-1] = t[j];
 				t[j] = tmp;

 				/* Le tableau n'est toujours pas trié */
				en_desordre = TRUE;
 			}
		}
	}
}

Tri par sélection[modifier | modifier le code]

Le tri par sélection (ou tri par extraction) est un des algorithmes de tri les plus triviaux. Il consiste en la recherche soit du plus grand élément (ou le plus petit) que l'on va replacer à sa position finale c'est-à-dire en dernière position (ou en première), puis on recherche le second plus grand élément (ou le second plus petit) que l'on va replacer également à sa position finale c'est-à-dire en avant-dernière position (ou en seconde), etc., jusqu'à ce que le tableau soit entièrement trié.

Le tri par sélection est intéressant lorsque les éléments sont aisément comparables mais coûteux à déplacer dans la structure. Ainsi, le nombre de comparaisons sera toujours supérieur ou égal à ce qui est nécessaire pour effectuer un tri par insertion ou un tri à bulles. Par contre, s'il n'est pas possible de faire des insertions dans la structure en temps constant (O(1)), le nombre d'échanges sera en moyenne très inférieur.

Propriétés[modifier | modifier le code]

Le nombre de comparaisons nécessaires pour un tri est de N(N+1)/2 (où N est la quantité de donnée à trier).
Le nombre d'échanges, lui, est de l'ordre de N.

Le tri par sélection est un tri sur place (les éléments sont triés dans la structure) mais n'est pas un tri stable (l'ordre d'apparition des éléments égaux n'est pas préservé).

Complexité[modifier | modifier le code]

Meilleur cas : O(n²), le tableau est déjà trié, on doit parcourir tout le tableau mais on peut économiser l'échange
Pire cas : O(n²), le tableau est trié en ordre inverse
Moyenne : O(n²)

Implémentations[modifier | modifier le code]

Algorithme : (attention « ⇐ » note l'affectation, et « ⇌ » note l'échange de valeur)

 tab_entiers[MAX]

 PROCEDURE selection (tab_entiers t)
    variable c:entier
 	POUR CHAQUE i entier  dans  [0 ;  MAX - 1 [
 		min ⇐ i
 		POUR CHAQUE j entier dans [ i+1 ; MAX [
 			SI t[j] < t[min] ALORS
 				min ⇐ j
 		SI min ≠ i ALORS
                        t[i] ⇌ t[min]

Une mise en œuvre simple du tri par sélection sur un tableau d'entiers en C :

typedef int tab_entiers[MAX];

void selection(tab_entiers t)
{
     int i, min, j , x;
     for(i = 0 ; i < MAX - 1 ; i++)
     {
         min = i;
         for(j = i+1 ; j < MAX ; j++)
              if(t[j] < t[min])
                  min = j;
         if(min != i)
         {
             x = t[i];
             t[i] = t[min];
             t[min] = x;
         }
     }
}

Tri par insertion[modifier | modifier le code]

Le tri par insertion est le tri le plus efficace sur des listes de petite taille. C'est pourquoi il est utilisé par d'autres méthodes comme le tri rapide (ou quicksort). Il est d'autant plus rapide que les données sont déjà triées en partie dans le bon ordre.

Le principe de ce tri est très simple: c'est le tri que toute personne utilise naturellement quand elle a des dossiers (ou n'importe quoi d'autre) à classer. On prend un dossier et on le met à sa place parmi les dossiers déjà triés. Puis on recommence avec le dossier suivant.

Pour procéder à un tri par insertion, il suffit de parcourir une liste : on prend les éléments dans l'ordre. Ensuite, on les compare avec les éléments précédents jusqu'à trouver la place de l'élément qu'on considère. Il ne reste plus qu'à décaler les éléments du tableau pour insérer l'élément considéré à sa place dans la partie déjà triée. On peut aussi faire une recherche par dichotomie sur les tableaux.

Une amélioration possible de ce tri, sensible pour les listes de plus de 15 éléments, est le tri de Shell.

Propriétés[modifier | modifier le code]

Dans le cas du tri par insertion sur un tableau comme implémenté plus bas (implémentation la plus courante), les propriétés suivantes sont vérifiées:

Le nombre de comparaisons nécessaires est de l'ordre de N²/4.
Le nombre moyen d'échanges est de l'ordre de N²/4.

Compter en terme d'échanges n'est pas forcément adéquat pour ce tri. En effet, on peut faire des copies successives des éléments décalés plutôt que de les échanger ce qui divise par deux le nombre d'accès aux éléments.

Si une liste chaînée est utilisée, il n'y a plus d'échanges à faire (les insertions se font en temps constant), mais le nombre de comparaisons pour trouver l'emplacement où insérer reste de l'ordre de N²/4 et il est difficile d'optimiser cette recherche.

A contrario, avec un tableau il est possible de faire un nombre de comparaisons de l'ordre de N.ln(N) en utilisant une recherche par dichotomie pour trouver l'emplacement où insérer l'élément. Néanmoins le nombre moyen d'échanges ne sera pas modifié, et l'algorithme reste peu efficace sur les grands tableaux par rapport au tri rapide.

Dans le cas d'une liste presque triée, où seules quelques comparaisons et échanges sont nécessaires par élément, l'implémentation la plus courante du tri par insertion est souvent la meilleure méthode de tri. Par contre, si les éléments sont dans l'ordre inverse au départ, il s'agit du pire des cas et il faut N*(N-1)/2 échanges.

Le tri par insertion est un tri stable (conservant l'ordre d'apparition des éléments égaux) et un tri en place (les éléments sont directement triés dans la structure).

Optimisations possibles[modifier | modifier le code]

On peut optimiser ce tri en commençant par un élément au milieu de la liste puis en triant alternativement les éléments après et avant. On peut alors insérer le nouvel élément soit à la fin, soit au début des éléments triés, ce qui divise par deux le nombre moyen d'éléments décalés.

Contrairement à l'optimisation de Shell, cette optimisation permet de garder la stabilité du tri.

Implémentations[modifier | modifier le code]

Algorithme

DEBUT
Const N=//Valeur positive
VAR:
    Tampon, i, k     :ENTIER
Tab:
    tableau(1..N)    :ENTIER

POUR( i <-- 2 à N )
   Tampon <--- Tab[i]
   k      <--- i

   TANTQUE(k>1 et Tab[k-1]>Tampon)
      Tab[k] <--- Tab[k-1]
      k      <--- k-1
   FINTANTQUE

   Tab[k] <--- Tampon
FINPOUR

FIN

Une mise en œuvre simple du tri par insertion sur un tableau de nombres entiers en C :

#define MAX 100

void insertion(int t[MAX]) 
{
    /* Spécifications externes : Tri du tableau t par insertion séquentielle */
    int i,p,j;
    int x;
 
    for (i = 1; i < MAX; i++) 
    {
        /* stockage de la valeur en i */
        x = t[i]; 
        
        /* recherche du plus petit indice p inférieur à i tel que t[p] >= t[i] */
        for(p = 0; t[p] < x; p++);
        /* p pointe une valeur de t supérieure à celle en i */ 
 
        /* décalage avant des valeurs de t entre p et i */         
        for (j = i-1; j >= p; j--) {
            t[j+1] = t[j]; 
        }   
        
        t[p] = x; /* insertion de la valeur stockée à la place vacante */
    }
}

Exemple[modifier | modifier le code]

Voici les étapes de l'exécution du tri par insertion sur le tableau $T=[9,6,1,4,8]$ . Le tableau est représenté au début et à la fin de chaque itération.

i=1

9	6	1	4	8

\rightarrow

6	9	1	4	8

i=2

6	9	1	4	8

\rightarrow

1	6	9	4	8

i=3

1	6	9	4	8

\rightarrow

1	4	6	9	8

i=4

1	4	6	9	8

\rightarrow

1	4	6	8	9

Tri par tas[modifier | modifier le code]

Une exécution de l'algorithme du tri par tas (Heapsort) trie une partie des valeurs permutées au hasard. Dans un premier temps, les éléments sont réarrangés pour respecter les conditions de tas. Avant le tri à proprement parler, la structure de l'arbre en tas est montrée brièvement par l'illustration.]] Le tri par tas est un algorithme de tri par comparaisons.

Cet algorithme est de complexité asymptotiquement optimale, c'est-à-dire qu'il est de complexité proportionnelle à $n\ \log \ n$ où $n$ est la longueur du tableau à trier ; il n'y a pas de pire des cas en $O(n^{2})$ comme avec le tri rapide. On démontre qu'aucun algorithme de tri par comparaison ne peut avoir de complexité asymptotiquement meilleure.

Par ailleurs, cet algorithme est en place, c'est-à-dire qu'il ne nécessite pas l'allocation d'une zone mémoire supplémentaire en sus de celle contenant les données d'entrée.

L'inconvénient majeur de ce tri est sa lenteur en moyenne comparée au tri rapide. En effet, le tri par tas est environ deux fois plus lent dans la plupart des cas.

Principe[modifier | modifier le code]

L'idée qui sous-tend cet algorithme consiste à voir le tableau comme un arbre binaire. Le premier élément est la racine, le deuxième et le troisième sont les deux descendants du premier élément, etc. Ainsi le $n$ ^ième élément a pour enfants les éléments $2n$ et $2n+1$ . Si le tableau n'est pas de taille $2^{n}$ , les branches ne se finissent pas tout à fait à la même profondeur.

Dans l'algorithme, on cherche à obtenir un tas, c'est-à-dire un arbre binaire vérifiant les propriétés suivantes (les deux premières propriétés découlent de la manière dont on considère les éléments du tableau) :

la différence maximale de profondeur entre deux feuilles est de 1 (i.e. toutes les feuilles se trouvent sur la dernière ou sur l'avant-dernière ligne) ;
les feuilles de profondeur maximale sont « tassées » sur la gauche.
chaque nœud est de valeur supérieure (resp. inférieure) à celles de ses deux fils, pour un tri ascendant (resp. descendant).

Comme expliqué plus haut, un tas ou un arbre binaire presque complet peut être stocké dans un tableau, en posant que les deux descendants de l'élément d'indice $n$ sont les éléments d'indices $2n$ et $2n+1$ (pour un tableau indicé à partir de 1). En d'autres termes, les nœuds de l'arbre sont placés dans le tableau ligne par ligne, chaque ligne étant décrite de gauche à droite.

Une fois le tas de départ obtenu, l'opération de base de ce tri est le tamisage, ou percolation, d'un élément, supposé le seul « mal placé » dans un arbre qui est presque un tas. Plus précisément, considérons un arbre $A=A[1]$ dont les deux sous-arbres ( $A[2]$ et $A[3]$ ) sont des tas, tandis que la racine est éventuellement plus petite que ses fils. L'opération de tamisage consiste à échanger la racine avec le plus grand de ses fils, et ainsi de suite récursivement jusqu'à ce qu'elle soit à sa place.

Pour construire un tas à partir d'un arbre quelconque, on tamise les racines de chaque sous-tas, de bas en haut (par taille croissante) et de droite à gauche.

Pour trier un tableau à partir de ces opérations, on commence par le transformer en tas. On échange la racine avec le dernier élément du tableau, et on restreint le tas en ne touchant plus au dernier élément, c'est-à-dire à l'ancienne racine. On tamise la racine dans le nouveau tas, et on répète l'opération sur le tas restreint jusqu'à l'avoir vidé et remplacé par un tableau trié.

Pseudo-code[modifier | modifier le code]

On fait l'hypothèse que arbre est un tableau indexé entre 1 et longueur. arbre[i] désigne le i-ème élément de ce tableau.

fonction tamiser(arbre,nœud,n): {descend arbre[nœud] à sa place, sans dépasser l'indice n}
  k:=nœud
  j:=2k
  tant que j<=n
    si j<n et arbre[j]<arbre[j+1]
      j:=j+1
    fin si
    si arbre[k]<arbre[j]
      échanger arbre[k] et arbre[j]
      k:=j
      j:=2k
    sinon
      terminer
    fin si
  fin tant que
fin fonction

fonction tri_par_tas(arbre,longueur):
  pour i:=longueur a 1
    tamiser(arbre,i,longueur)
  fin pour
  pour i:=longueur a 2
    échanger arbre[i] et arbre[1]
    tamiser(arbre,1,i-1)
  fin pour
fin fonction

À la fin de la fonction tri_par_tas le tableau arbre est trié suivant l'ordre croissant. Il suffit d'inverser les opérateurs de comparaison pour obtenir un tri dans l'ordre décroissant.

Analyse[modifier | modifier le code]

Cet algorithme permet de trier sur place les éléments d'un tableau en un temps de l'ordre de $n\ \log _{2}\ n$ dans le pire des cas, où $n$ est le nombre d'éléments à trier. Les principaux atouts de cette méthode sont la faible consommation mémoire et l'efficacité optimale, étant donné qu'on ne fait aucune hypothèse sur la nature des données à trier.

Amélioration possible[modifier | modifier le code]

Quand le tableau est déjà trié, le tri par tas le mélange d'abord avant de le retrier. L'algorithme Smoothsort a pour but de pallier cet inconvénient.

A la fin du tri par tas, pour les 15 derniers éléments environ, l'algorithme effectue plusieurs fois de suite les mêmes inversions, ce qui est inutile. On peut à la place arrêter l'algorithme quand il n'y a plus beaucoup d'éléments et passer à un autre. Les données qui restent sont à peu près triées à l'envers. On peut donc, par exemple :
- retourner les données restantes (avec une inversion du 1^er et du dernier, du 2^e et de l'avant-dernier etc.) puis effectuer un tri par insertion.
- ou effectuer un tri rapide sur les données restantes (on est dans un bon cas avec un tableau à peu près à l'envers), ce qui peut se faire déjà avec les 25 éléments restants

Implémentation[modifier | modifier le code]

This code will sort an integer array using Heap Sort algorithm

#include<stdio.h>
#include<conio.h>
#include<math.h>


void swap(int *p, int *q);
void HEAPSORT(int heap[100], int n);
int BUILD_HEAP(int heap[100],int n);
void HEAPIFY(int heap[100], int i, int heap_size);

int PARENT(int i);
int LEFT(int i);
int RIGHT(int i);

//int heap_size;

void main()
{
int i,j,n;
int heap[110];

while(1)
	{
	printf("Enter the number of element (0 to exit): ");
	scanf("%d",&n);
	if(n==0)
		break;
	for(i=1;i<=n;++i)
		scanf("%d",&heap[i]);
	HEAPSORT(heap,n);
	printf("The sorted List is:\n");
	for(i=1;i<=n;++i)
		printf("%d ",heap[i]);
	}
}

void HEAPSORT(int heap[100], int n)
{
int i,heap_size;
heap_size = BUILD_HEAP(heap,n);
for(i=n;i>=2;--i)
	{
	swap(&heap[1],&heap[i]);
	--heap_size;
	HEAPIFY(heap,1,heap_size);
	}

}

void swap(int *p, int *q)
{
int t;
t=*p;
*p=*q;
*q=t;
}

int BUILD_HEAP(int heap[100],int n)
{
int i, heap_size;
heap_size = n;
for(i=floor(n/2);i>=1;--i)
	HEAPIFY(heap,i,heap_size);
return heap_size;
}

void HEAPIFY(int heap[100], int i, int heap_size)
{
int l,r,largest;
l = LEFT(i);
r = RIGHT(i);

if(l <= heap_size && heap[l] > heap[i])
	largest = l;
else
	largest = i;
if(r <= heap_size && heap[r] > heap[largest])
	largest = r;
if(largest != i)
	{
	swap(&heap[i],&heap[largest]);
	HEAPIFY(heap,largest,heap_size);
	}

}

int PARENT(int i)
	{return (i/2);}
int LEFT(int i)
	{return (2*i);}
int RIGHT(int i)
	{return ((2*i)+1);}

another c code

/*  Heapsort based on ideas of J.W.Williams/R.W.Floyd/S.Carlsson  */
 
 #define  data_i_LESS_THAN_(other)   (data[i] < other)
 #define  MOVE_i_TO_free  { data[free]=data[i];  free=i; }
 
 void sift_in(unsigned count, SORTTYPE *data, unsigned free_in,
 SORTTYPE next)
 {
    unsigned i;
    unsigned free = free_in;
    // sift down the free node 
    for (i=2*free;i<count;i+=i)
    {  if (data_i_LESS_THAN_(data[i+1]))  i++;
       MOVE_i_TO_free
    }
    // special case in sift down if the last inner node has only 1 child
    if (i==count)
       MOVE_i_TO_free
    // sift up the new item next 
    while( ((i=free/2)>=free_in)   &&  data_i_LESS_THAN_(next))
       MOVE_i_TO_free
    data[free] = next;
 }
 
 void heapsort(unsigned count, SORTTYPE *data)
 {
    unsigned  j;
 
    if (count <= 1)  return;
    data-=1;   // map addresses to indices 1 til count
    // build the heap structure 
    for(j=count / 2; j>=1; j--) {
       SORTTYPE  next = data[j];
       sift_in(count, data, j, next);
    }
 
    // extract extremal element and sift_in next element
    for(j= count - 1; j>=1; j--) {
       SORTTYPE next = data[j + 1];
       data[j + 1] = data[1];   // extract extremal element from the heap
       sift_in(j, data, 1, next);
    }
 }

Tri rapide[modifier | modifier le code]

Le tri rapide (en anglais quicksort) est une méthode de tri inventée par C.A.R. Hoare en 1961 et fondée sur la méthode de conception diviser pour régner. Il peut être implémenté sur un tableau (tri sur place) ou sur des listes ; son utilisation la plus répandue concerne tout de même les tableaux.

Le Quicksort est un tri dont la complexité moyenne est en $O(n\ \log n)$ , mais dont la complexité dans le pire des cas est $O(n^{2})$ . Malgré ce désavantage théorique, c'est en pratique un des tris sur place le plus rapide pour des données réparties aléatoirement. Les entrées donnant lieu au comportement quadratique dépendent de l'implémentation de l'algorithme, mais sont souvent (si l'implémentation est maladroite) les entrées déjà presque triées. Il sera plus avantageux alors d'utiliser le tri par insertion ou l'algorithme Smoothsort.

Performance et algorithme[modifier | modifier le code]

La méthode consiste à placer un élément d'un tableau d'éléments à trier (appelé pivot) à sa place définitive en permutant tous les éléments de telle sorte que tous ceux qui lui sont inférieurs soient à sa gauche et que tous ceux qui lui sont supérieurs soient à sa droite. Cette opération s'appelle le partitionnement. Pour chacun des sous-tableaux, on définit un nouveau pivot et on répète l'opération de partitionnement. Ce processus est répété récursivement, jusqu'à ce que l'ensemble des éléments soit trié.

  tri_rapide(tableau t, entier premier, entier dernier)
    début
      si premier < dernier alors
        pivot <- choix_pivot(t,premier,dernier)
        pivot <- partitionner(t,premier,dernier,pivot)
        tri_rapide(t,premier,pivot-1)
        tri_rapide(t,pivot+1,dernier)
      finsi
    fin

Si le pivot est correctement choisi à chaque étape, c'est une des méthodes de tri les plus rapides dans le cas moyen (entrée triée dans un ordre aléatoire uniformément distribué), avec une complexité algorithmique en O(n ln(n)). Cette complexité peut se dégrader en O(n²) dans le pire des cas, qui se trouve être celui où les éléments sont déjà dans l'ordre pour certaines implémentations. Comme ce pire cas est finalement assez courant (tri de listes quasiment déjà triées), on se ramène parfois au cas moyen en appliquant une permutation aléatoire uniformément distribuée sur les entrées ou bien on choisit aléatoirement le pivot.

Dans la pratique, pour les partitions avec un faible nombre d'éléments (jusqu'à environ 15 éléments), on a souvent recours à un tri par insertion qui se révèle plus efficace que le tri rapide.

Grâce à ses bonnes performances et à son implémentation facile (en première approche), quicksort est l'un des algorithmes de tri les plus répandus.

Le tri rapide n'est pas un tri stable car il ne préserve pas nécessairement l'ordre des éléments possédant une clef de tri identique. On peut cependant compenser ce problème en ajoutant l'information sur la position de départ à chaque élément et en ajoutant un test sur la position en cas d'égalité sur la clef de tri.

Le problème le plus important est le choix du pivot. Une implémentation du tri rapide qui ne choisit pas adéquatement le pivot sera très inefficace pour certaines entrées. Par exemple, si le pivot est toujours le plus petit élément de la liste, QuickSort sera aussi efficace qu'un tri par sélection, c'est-à-dire de performance O(n²).

Enfin, un problème lié est le niveau de récursion: dans le pire des cas il peut être linéaire: la pile requiert un espace supplémentaire de O(n).

Choisir un meilleur pivot[modifier | modifier le code]

Le pire cas du tri rapide n'est pas qu'un problème théorique. Quand il est utilisé avec des services Web, par exemple, il est possible pour un attaquant d'utiliser volontairement des données conduisant au pire cas de performance et de provoquer un ralentissement de la machine attaquée voire un arrêt intempestif du programme par débordement de pile.

Des données triées ou partiellement triées sont relativement fréquentes dans la pratique et l'implémentation naïve du tri rapide qui choisit le premier élément comme pivot conduit à une profondeur de récursivité linéaire. Pour résoudre ce problème, on peut utiliser l'élément du milieu du tableau. Cette façon de faire fonctionne bien pour les listes déjà triées ou à l'envers mais facilite la mise au point d'attaques.

Une meilleure optimisation peut consister par exemple à sélectionner le pivot aléatoirement entre 2 valeurs au centre, pour éviter que les pirates puissent prévoir la réaction de votre méthode de tri en fonction des données à trier.

Si le nombre d'éléments est suffisamment grand pour le justifier, on peut envisager de rechercher la valeur médiane de la liste, mais en pratique cela en vaut rarement la peine.

Autres optimisations[modifier | modifier le code]

Une optimisation utile, déjà mentionnée plus haut, consiste à changer d'algorithme lorsque le sous-ensemble de données non encore trié devient petit. La taille optimale des sous-listes est d'environ 15 éléments. On peut alors utiliser le tri par sélection ou le tri par insertion. Le tri par sélection ne sera sûrement pas efficace pour un grand nombre de données, mais il est souvent plus rapide que le tri rapide sur des listes courtes, du fait de sa plus grande simplicité.

Robert Sedgewick 1978 suggère une amélioration (appelée Sedgesort) lorsqu'on utilise un tri simplifié pour les petites sous-listes : on peut diminuer le nombre d'opérations nécessaires en différant le tri des petites sous-listes après la fin du tri rapide, après quoi on exécute un tri par insertion sur le tableau entier.

LaMarca et Ladner 1997 ont étudié « l'influence des caches sur les performances des tris », un problème prépondérant sur les architectures récentes dotées de hiérarchies de caches avec des temps de latence élevés lors des échecs de recherche de données dans les caches. Ils concluent que, bien que l'optimisation de Sedgewick diminue le nombre d'instructions exécutées, elle diminue aussi le taux de succès des caches à cause de la plus large dispersion des accès à la mémoire (lorsque l'on fait le tri par insertion à la fin sur tout le tableau et non au fur et à mesure), ce qui entraine une dégradation des performances du tri. Toutefois l'effet n'est pas dramatique et ne devient significatif qu'avec des tableaux de plus de 4 millions d'éléments de 64 bits. Cette étude est citée par Musser.

Étant donné que le tri rapide nécessite davantage de mémoire pour implémenter la récursion, des variantes non récursives du tri rapide ont été écrites. Elles ont l'avantage d'utiliser la mémoire de façon plus prévisible, indépendante des données à trier, au prix d'une très nette augmentation de la complexité du code. Les programmeurs voulant utiliser un tri itératif peuvent envisager d'utiliser Introsort, le tri par tas et Smoothsort.

Une autre solution simple pour réduire l'utilisation de la mémoire par un tri rapide utilise une récursion pour la plus petite des sous-listes à trier, et une récursion finale (qui peut donc être transformée en une boucle) pour la plus grande. Ceci limite la quantité de mémoire utilisée a O(log n). Par exemple:

tri_rapide(a, gauche, droite)
    tant que droite-gauche+1 > 1
        sélectionner une valeur de pivot a[pivotIndex]
        pivotNewIndex := partition(a, gauche, droit, pivotIndex)
        si pivotNewIndex-1 - gauche < droit - (pivotNewIndex+1)
            tri_rapide(a, gauche, pivotNewIndex-1)
            gauche := pivotNewIndex+1
        sinon
            tri_rapide(a, pivotNewIndex+1, droit)
            droit := pivotNewIndex-1
        fin_si
   fin_tant_que

Algorithmes de tri en n.log(n)[modifier | modifier le code]

Une variante du tri rapide devenu largement utilisée est introsort alias introspective sort (Musser 1997). Elle démarre avec un tri rapide puis utilise un tri par tas lorsque la profondeur de récursivité dépasse une certaine limite prédéfinie. Elle permet d'éviter la complexité du choix d'un bon pivot tout en garantissant une exécution en O(n log n).

Sinon, on peut utiliser à la place du tri rapide un tri par tas pur. Le tri par tas est en moyenne plus lent que le tri rapide mais son plus mauvais comportement est en O(n log n), aussi il est préféré lorsque la complexité maximale doit être garantie ou lorsque l'on soupçonne que le comportement en O(n²) du tri rapide sera souvent atteint. Le tri par tas a aussi l'avantage de requérir un espace mémoire additionnel constant tandis que la meilleure variante du tri rapide utilise O(log n) d'espace mémoire additionnel.

Un inconvénient majeur du tri par tas est que si la liste est déjà triée, elle sera mélangée par l'algorithme avant d'être retriée. L'algorithme Smoothsort a pour but de pallier ce problème.

Relation avec le tri par sélection[modifier | modifier le code]

Un algorithme de sélection simple, qui choisit le plus petit des éléments d'une liste, fonctionne globalement de la même manière que le quicksort, la différence étant qu'au lieu d'être appelé récursivement sur les deux sous-listes, il n'est appelé récursivement que sur la sous-liste contenant l'élément recherché. Cette petite différence fait passer la complexité moyenne à un niveau linéaire, en O(n). Une variante de cet algorithme trouve la valeur médiane à chaque étape, ce qui réduit également le temps d'exécution dans le pire des cas à O(n).

Implémentations[modifier | modifier le code]

Une mise en œuvre simple de QuickSort sur un tableau d'entiers en C :

void quickSort(int *tableau, int p, int r) {
	int q;
	if(p<r) {
		q = partitionner(tableau, p, r);
		quickSort(tableau, p, q);
		quickSort(tableau, q+1, r);
	}
}

int partitionner(int *tableau, int p, int r) {
	int pivot = tableau[p], i = p-1, j = r+1;
	int temp;
	while(1) {
		do
			j--;
		while(tableau[j] > pivot);
		do
			i++;
		while(tableau[i] < pivot);
		if(i<j) {
			temp = tableau[i];
 			tableau[i] = tableau[j];
 			tableau[j] = temp;
 		}
 		else
                        return j;
        }
        return j;
}

Tri par dénombrement[modifier | modifier le code]

Le tri par dénombrement (appelé aussi tri casier) est un algorithme de tri qui s'applique sur des valeurs entières.

Définition[modifier | modifier le code]

Le principe repose sur la construction de l'histogramme des données, puis le balayage de celui-ci de façon croissante, afin de reconstruire les données triées.

Ici, la notion de stabilité (tri stable) n'a pas réllement de sens, puisque l'histogramme factorise les données (c.a.d plusieurs éléments identiques seront représentés par un unique élément quantifié). Ce tri ne peut donc pas être appliqué sur des structures complexes, et il convient exclusivement aux données constituées de nombres entiers compris entre une borne min et une borne max connues. Dans un souci d'efficacité, celles-ci doivent être relativement proches l'une d'elle, ainsi que le nombre d'éléments doit être relativement grand.

Dans cette configuration, et avec une distribution de données suivant une loi uniforme, ce tri est le plus rapide (on troque, en quelque sorte, du temps de calcul contre de la mémoire).

La restriction très particulière imposée à ses valeurs d'entrée en fait un tri en temps linéaire, alors qu'un tri par comparaisons optimal nécessite un nombre d'opérations de l'ordre de $n\log n$ .

Exemple[modifier | modifier le code]

On suppose qu'on dispose d'un tableau tab composé de 100 entiers entre 0 et 30 (bornes comprises).

Le procédé du tri par comptage est le suivant : on compte le nombre des "0", le nombre des "1", ..., le nombre des "30" présents dans tab, et on reconstruit tab en y ajoutant les valeurs selon leur quantité croissante (on ne trie pas les valeurs mais le comptage de ces valeurs au sein du tableau).

Le tableau de 5 entiers 1, 27, 3, 1, 3 contient 2 fois 1, 2 fois 3 et 1 fois 27, le tableau trié par la méthode du tri comptage est donc : 1, 1, 3, 3, 27

Tableau avant et après triage :

x	1	2	3	4	5
tab[x]	1	27	3	1	3
tab[x] trié	1	1	3	3	27

Tableau de comptage :

x	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27
tab_comptage[x]	0	2	0	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1

Algorithme[modifier | modifier le code]

L'algorithme présenté ici n'est pas la seule solution au problème, et n'est peut-être pas le plus optimal. Le signe ⇐ est utilisé pour les affectations.

Le tableau tab est le tableau à trier, et est passé en paramètre de la fonction tri_par_comptage. La variable borne_superieure, est la valeur entière maximale présente dans tab.

On considère que l'index des tableaux commence à 0.

La fonction tri_par_comptage utilise des variables intermédiaires :

tab_comptage, est un tableau contenant n éléments, n étant la valeur maximale dans tab.
i et j sont des variables de type entier, servant à parcourir les tableaux tab et tab_comptage.

fonction tri_par_comptage(tableau tab, entier borne_superieure)
 
   /* Initialisation des variables */
 
   tab_comptage[borne_superieure + 1]
   taille_tab ⇐ taille(tab) - 1
 
   /* Initialisation du tableau de comptage à 0 */
 
   Pour i ⇐ 0 Jusqu'à borne_superieure
   Faire
      tab_comptage[ i ] ⇐ 0
   FinPour
 
   /* Création du tableau de comptage */
 
   Pour i ⇐ 0 Jusqu'à taille_tab
   Faire
      tab_comptage[ tab[ i ] ] ⇐ tab_comptage[ tab[ i ] ] + 1
   FinPour
 
   /* Création du tableau trié */
 
   l ⇐ 0
   Pour i ⇐ 0 Jusqu'à borne_superieure
   Faire
      Pour j ⇐ 1 Jusqu'à tab_comptage[i]
      Faire
         tab[l] = i
         l ⇐ l + 1
      FinPour
   FinPour
 
 Retourne tab

Implémentation[modifier | modifier le code]

L'implémentation est triviale en C :

#define MAX 256 // borne min = 0 et borne max = 255 incluses

void tri_hist(int t[], int len)
{
	int i, j, k;
	int * hist = calloc(MAX, sizeof(int));

	for(i=0; i < len; i++)
		hist[ t[i] ]++;

	k=0;
	for(i=0; i < MAX; i++)
		for(j=0; j < hist[i]; j++)
			t[k++] = i;

	free(hist);
}