Tri par insertion (∼90mn – moyen)
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.
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) :
Mettez en œuvre cet algorithme.
