Tri par sélection

(Rien ne semble avoir changé sur ces deux dernières lignes car les deux derniers numéros étaient déjà dans l'ordre.)

Le tri par sélection peut également être utilisé sur des structures de liste qui rendent l'ajout et la suppression efficaces, comme une liste chaînée . Dans ce cas, il est plus courant de supprimer l'élément minimum du reste de la liste, puis de l' insérer à la fin des valeurs triées jusqu'à présent. Par exemple :

arr[] = 64 25 12 22 11 // Trouver l'élément minimum dans arr[0...4] // et placez-le au début 11 25 12 22 64 // Trouver l'élément minimum dans arr[1...4] // et placez-le au début de arr[1...4] 11 12 25 22 64 // Trouver l'élément minimum dans arr[2...4] // et placez-le au début de arr[2...4] 11 12 22 25 64 // Trouver l'élément minimum dans arr[3...4] // et placez-le au début de arr[3...4] 11 12 22 25 64 

Vous trouverez ci-dessous une implémentation en C .

/* a[0] à a[aLength-1] est le tableau à trier */
j , j ;​
int aLength ; // initialiser à la longueur de a
/* avancer la position sur l'ensemble du tableau */
/* (pourrait faire i < aLength-1 car un seul élément est également un élément minimum) */
pour ( i = 0 ; i < aLongueur -1 ; i ++ )
{
/* trouver l'élément minimum dans le a[i .. aLength-1] non trié */
/* suppose que le minimum est le premier élément */
int jMin = i ;
/* tester sur les éléments après i pour trouver le plus petit */
pour ( j = i + 1 ; j < aLongueur ; j ++ )
{
/* si cet élément est inférieur, alors c'est le nouveau minimum */
si ( a [ j ] < a [ jMin ])
{
/* nouveau minimum trouvé ; mémoriser son index */
jMin = j ;
}
}
si ( jMin != i )
{
échanger ( &a a [ je ], &a a [ jMin ]);
}
}

Le tri par sélection n'est pas difficile à analyser par rapport aux autres algorithmes de tri, car aucune des boucles ne dépend des données du tableau. La sélection du minimum nécessite de scanner les éléments (effectuer des comparaisons), puis de les placer en première position. Trouver l'élément suivant le plus bas nécessite de scanner les éléments restants (effectuer des comparaisons) et ainsi de suite. Par conséquent, le nombre total de comparaisons est

Par progression arithmétique ,

qui est d'une complexité en termes de nombre de comparaisons.

Parmi les algorithmes de tri quadratique (algorithmes de tri avec un cas moyen simple de Θ( n ² ) ), le tri par sélection surpasse presque toujours le tri à bulles et le tri gnome . Le tri par insertion est très similaire dans la mesure où, après la k ième itération, les premiers éléments du tableau sont triés. L'avantage du tri par insertion est qu'il analyse uniquement le nombre d'éléments dont il a besoin pour placer le st élément, tandis que le tri par sélection doit analyser tous les éléments restants pour trouver le st élément.

Un calcul simple montre que le tri par insertion effectue donc généralement environ la moitié moins de comparaisons que le tri par sélection, bien qu'il puisse en effectuer autant ou beaucoup moins selon l'ordre dans lequel se trouvait le tableau avant le tri. On peut considérer comme un avantage pour certaines applications en temps réel que le tri par sélection fonctionne de manière identique quel que soit l'ordre du tableau, alors que le temps d'exécution du tri par insertion peut varier considérablement. Cependant, cela constitue plus souvent un avantage pour le tri par insertion dans la mesure où il s'exécute beaucoup plus efficacement si le tableau est déjà trié ou « presque trié ».

Bien que le tri par sélection soit préférable au tri par insertion en termes de nombre d'écritures ( swaps par rapport à jusqu'à swaps, chaque swap représentant deux écritures), cela représente environ le double du minimum théorique atteint par le tri par cycle , qui effectue au plus n écritures. Cela peut être important si les écritures sont nettement plus coûteuses que les lectures, comme avec l'EEPROM ou la mémoire Flash , où chaque écriture réduit la durée de vie de la mémoire.

Le tri par sélection peut être implémenté sans branches imprévisibles au profit des prédicteurs de branches du processeur , en trouvant l'emplacement du minimum avec un code sans branche, puis en effectuant l'échange sans condition.

Enfin, le tri par sélection est largement surpassé sur les tableaux plus grands par les algorithmes de division et de conquête tels que mergesort . Cependant, le tri par insertion ou le tri par sélection sont tous deux généralement plus rapides pour les petits tableaux (c'est-à-dire moins de 10 à 20 éléments). Une optimisation utile dans la pratique pour les algorithmes récursifs consiste à passer au tri par insertion ou au tri par sélection pour les sous-listes « suffisamment petites ».

Le tri par tas a été décrit comme « rien d'autre qu'une implémentation du tri par sélection utilisant la bonne structure de données ». Il améliore considérablement l'algorithme de base en utilisant une structure de données de tas implicite pour trouver et supprimer chaque élément le plus bas dans le temps, au lieu de la boucle interne du tri par sélection normal, réduisant ainsi le temps d'exécution total à .

Une variante bidirectionnelle du tri par sélection (appelée tri par double sélection ou parfois tri cocktail en raison de sa similitude avec le tri cocktail shaker ) trouve à la fois les valeurs minimales et maximales de la liste à chaque passage. Cela nécessite trois comparaisons par deux éléments (une paire d'éléments est comparée, puis le plus grand est comparé au maximum et le plus petit est comparé au minimum) plutôt qu'une comparaison par élément du tri par sélection classique, mais ne nécessite que la moitié des passages, soit une économie nette de 25 %.

Le tri par sélection peut être implémenté comme un tri stable si, au lieu d'effectuer un échange à l'étape 2, la valeur minimale est insérée dans la première position et les valeurs intermédiaires décalées vers le haut. Cependant, cette modification nécessite soit une structure de données qui prend en charge des insertions ou des suppressions efficaces, comme une liste chaînée, soit elle conduit à effectuer des écritures.

Dans la variante de tri bingo , les éléments sont triés en parcourant à plusieurs reprises les éléments restants pour trouver la plus grande valeur et en déplaçant tous les éléments avec cette valeur vers leur emplacement final. Comme le tri par comptage , il s'agit d'une variante efficace s'il existe de nombreuses valeurs en double : le tri par sélection effectue un passage dans les éléments restants pour chaque élément déplacé, tandis que le tri bingo effectue un passage pour chaque valeur . Après un passage initial pour trouver la plus grande valeur, les passages suivants déplacent chaque élément avec cette valeur vers son emplacement final tout en recherchant la valeur suivante comme dans le pseudo-code suivant (les tableaux sont basés sur zéro et la boucle for inclut à la fois les limites supérieure et inférieure, comme en Pascal ) :

bingo ( tableau A )
{ Cette procédure trie par ordre croissant en 
 déplaçant à plusieurs reprises le nombre maximal d'éléments vers la fin. } 
begin 
last := length ( A ) - 1 ;
{ La première itération est écrite pour ressembler beaucoup aux 
 suivantes, mais sans échanges. } 
nextMax := A [ last ] ; for i := last - 1 downto 0 do if A [ i ] > nextMax then nextMax := A [ i ] ; while ( last > 0 ) and ( A [ last ] = nextMax ) do last := last - 1 ;
while last > 0 do begin { Chaque boucle principale recherche le nouveau nextMax tout en  échangeant les éléments égaux à prevMax en place. } prevMax := nextMax ; nextMax := A [ last ] ; for i := last - 1 downto 0 do if A [ i ] > nextMax then if A [ i ] <> prevMax then nextMax := A [ i ] ; else begin swap ( A [ i ] , A [ last ]) ; last := last - 1 ; end while ( last > 0 ) and ( A [ last ] = nextMax ) do last := last - 1 ; end ; end ;

Ainsi, si en moyenne il y a plus de deux éléments avec la même valeur, on peut s'attendre à ce que le tri par bingo soit plus rapide car il exécute la boucle interne moins de fois que le tri par sélection.