algorithm
Tri par insertion
Recherche…
Remarques
Lorsque nous analysons les performances de l'algorithme de tri, nous nous intéressons principalement au nombre de comparaison et d'échange.
Échange moyen
Soit E n le nombre total moyen d'échange à trier le tableau de l'élément N. E 1 = 0 (nous n'avons besoin d'aucun échange pour le tableau avec un élément). Le nombre moyen d'échanges pour trier le tableau d'éléments N est la somme du nombre moyen de numéros d'échange pour trier le tableau d'éléments N-1 avec le commutateur moyen pour insérer le dernier élément dans le tableau d'éléments N-1.
Simplifier la sommation (séries arithmétiques)
Élargit le terme
Simplifier la sommation à nouveau (séries arithmétiques)
Comparaison moyenne
Soit C n le nombre total moyen de comparaison pour trier le tableau de l'élément N. C 1 = 0 (nous n'avons pas besoin de comparaison sur un tableau d'éléments). Le nombre moyen de comparaison pour trier le tableau d'éléments N est la somme du nombre moyen de nombres de comparaison pour trier le tableau d'éléments N-1 avec la comparaison moyenne pour insérer le dernier élément dans le tableau d'éléments N-1. Si le dernier élément est le plus grand élément, nous n'avons besoin que d'une seule comparaison, si le dernier élément est le deuxième plus petit élément, nous avons besoin d'une comparaison N-1. Cependant, si le dernier élément est le plus petit élément, nous n'avons pas besoin de comparaison N. Nous avons toujours besoin de la comparaison N-1. C'est pourquoi nous supprimons 1 / N dans l'équation ci-dessous.
Simplifier la sommation (séries arithmétiques)
Développez le terme
Simplifier la sommation à nouveau (séries arithmétiques et nombre harmonique)
Bases de l'algorithme
Le tri par insertion est un algorithme de tri très simple, stable et en place. Il fonctionne bien sur les petites séquences mais il est beaucoup moins efficace sur les grandes listes. A chaque étape, l'algorithme considère le i-ème élément de la séquence donnée, en le déplaçant vers la gauche jusqu'à ce qu'il soit dans la bonne position.
Illustration graphique
Pseudocode
for j = 1 to length(A)
n = A[j]
i = j - 1
while j > 0 and A[i] > n
A[i + 1] = A[i]
i = i - 1
A[i + 1] = n
Exemple
Considérons la liste suivante d'entiers:
[5, 2, 4, 6, 1, 3]
L'algorithme effectuera les étapes suivantes:
-
[5, 2, 4, 6, 1, 3] -
[2, 5, 4, 6, 1, 3] -
[2, 4, 5, 6, 1, 3] -
[2, 4, 5, 6, 1, 3] -
[1, 2, 4, 5, 6, 3] -
[1, 2, 3, 4, 5, 6]
Implémentation C #
public class InsertionSort
{
public static void SortInsertion(int[] input, int n)
{
for (int i = 0; i < n; i++)
{
int x = input[i];
int j = i - 1;
while (j >= 0 && input[j] > x)
{
input[j + 1] = input[j];
j = j - 1;
}
input[j + 1] = x;
}
}
public static int[] Main(int[] input)
{
SortInsertion(input, input.Length);
return input;
}
}
Espace auxiliaire: O(1)
Complexité temporelle: O(n)
Implantation Haskell
insertSort :: Ord a => [a] -> [a]
insertSort [] = []
insertSort (x:xs) = insert x (insertSort xs)
insert :: Ord a => a-> [a] -> [a]
insert n [] = [n]
insert n (x:xs) | n <= x = (n:x:xs)
| otherwise = x:insert n xs