Dans cet exercice, nous nous intéressons au tri par insertion.
Le principe de cet algorithme est de maintenir un ensemble trié lors de l'insertion d'un nouvel
élément.
Vous pouvez observer une mise en œuvre intéressante de cet algorithme
ici.
L'algorithme de tri par insertion est particulièrement efficace pour de petits ensembles
à trier, mais totalement inefficace dès que le nombre d'éléments devient grand.
Dans le projet tri, créez une classe
InsertionSort contenant une méthode main.
Affichez les arguments de votre programme après avoir spécifié que les arguments
sont 4 6 -1 3 5 2.
Créez un tableau tab contenant les arguments du programme, mais représentés par des
double.
double[] tab = new double[args.length];
for (int i = 0; i
Créez une méthode classe sort prenant en entrée un tableau de double et retournant
un tableau de double.
Dans cette méthode, créez un tableau nommé sorted ayant autant de cases que le tableau
des arguments du programme. La méthode doit retourner ce tableau.
Complétez votre programme de façon à afficher les éléments du tableau sorted dans la fonction
main. Pour cela, appelez la fonction sort sur tab et récupérez la sortie (non triée pour l'instant).
Votre programme devrait afficher 6 fois l'entier 0 puisque vous avez 6 arguments et parce qu'un
tableau est toujours pré-initialisé avec des 0 en Java.
Pour ajouter les valeurs au tableau sorted tout en maintenant le tableau trié,
vous devez itérer sur les arguments.
Pour chaque argument, vous devez procéder en trois étapes.
- Étape 1: à l'aide d'une boucle, trouvez l'emplacement dest
auquel il faut insérer l'argument courant dans le tableau sorted.
Pour cela, il suffit de trouver le premier élément qui est plus grand que l'argument à insérer.
Notez que vous ne devez comparer que les éléments déjà insérés (c'est-à-dire que vous devez
compter le nombre d'éléments insérés dans votre tableau, ça vous évitera de parcourir
tout le tableau à chaque fois).
- Étape 2: ensuite, décalez d'un cran à droite la partie se trouvant à droite de dest
dans le tableau sorted de façon à libérer un espace
pour le nouvel entier. Pensez à copier de la droite vers la gauche pour éviter d'écraser
vos valeurs.
- Étape 3: enfin, insérez le nouvel élément à l'emplacement dest.
Le petit schéma suivant illustre le principe (un point d'interrogation
indique qu'aucun élément n'est encore inséré à cet emplacement dans le tableau) :
Insertion de l'élément 8:
État initial:
Nombre d'éléments déjà insérés: 0
Tableau: [? ? ? ? ? ?]
Étape 1: Trouver la position à laquelle insérer l'élément
Emplacement d'insertion: 0 (car 8 est plus grand que tous les éléments déjà insérés)
Étape 2: Décaler d'un cran à droite la partie droite du tableau
Nombre d'éléments déjà insérés: 0
Tableau: [? ? ? ? ? ?]
Étape 3: Insérer l'élément 8
Nombre d'éléments déjà insérés: 1
Tableau: [8 ? ? ? ? ?]
...
Insertion de l'élément 3:
État initial:
Nombre d'éléments déjà insérés: 3
Tableau: [1 6 8 ? ? ?]
Étape 1: Trouver la position à laquelle insérer l'élément
Emplacement d'insertion: 2 (car l'élément 6 est plus grand que l'élément 3 à insérer)
Étape 2: Décaler d'un cran à droite la partie droite du tableau
Nombre d'éléments déjà insérés: 3
Tableau: [1 6 6 8 ? ?]
Étape 3: Insérer l'élément 3
Nombre d'éléments déjà insérés: 4
Tableau: [1 3 6 8 ? ?]
Commencez par écrire une fonction findInsertion qui prend en entrée un tableau de double (ce sera sorted),
l'élément à insérer, et l'indice de fin du tableau et qui retourne un entier représentant la position où
insérer notre élément.
static int findInsertion(double[] sorted, double value, int insertedCount) {
// On cherche le premier élément strictement plus grand que 'value'
for (int i = 0; i value) {
return i;
}
}
// Si aucun élément n'est plus grand, on insère en fin de la partie utilisée
return insertedCount;
}
Écrivez un fonction shift prenant en entrée un tableau de double et un indice. Cette
fonction décale en place tous les éléments du tableau d'un cran vers la droite à partir de l'indice donné (et
ne retourne rien).
static void shift(double[] sorted, int fromIndex, int insertedCount) {
for (int i = insertedCount; i > fromIndex; i--) {
sorted[i] = sorted[i - 1];
}
// La case 'fromIndex' sera écrasée par l'insertion qui suit
}
Finalement, implémentez la fonction sort.
static double[] sort(double[] input) {
double[] sorted = new double[input.length]; // pré-initialisé à 0.0
int insertedCount = 0;
for (int i = 0; i
Quelle est la complexité du tri par insertion dans le pire des cas ?
Dans le pire des cas, le tableau est trié dans l’ordre décroissant. Chaque nouvel élément doit être inséré tout au début.
Donc pour le i-ème élément, il faut décaler i cases. Nombre total de décalages/comparaisons ≈ 1 + 2 + … + (n-1) = n(n-1)/2.
On a une complexité de O(n²).
