#include "sort.h"
#include "system.h"
#include "stdio.h"

//---- insertion sort : non adapté pour tableaux de grande taille (> 100) --
void sort_insertion(unsigned int *base, unsigned int n) 
{
    /* Spécifications externes : Tri du tableau base par insertion séquentielle */
    int i,p,j;
    int x;

    for (i = 1; i < n; i++) 
    {

#if VERBOSE_SORT
        printf("-"); // added for debug
#endif
        /* stockage de la valeur en i */
        x = base[i]; 
 
        /* recherche du plus petit indice p inférieur à i tel que base[p] >= base[i] */
        for(p = 0; base[p] < x; p++);
        /* p pointe une valeur de base supérieure à celle en i */ 
 
        /* décalage avant des valeurs de base entre p et i */         
        for (j = i-1; j >= p; j--) {
            base[j+1] = base[j]; 
        }   
 
        base[p] = x; /* insertion de la valeur stockée à la place vacante */

#if VERBOSE_SORT
        printf("+"); // added for debug
#endif
    }
#if VERBOSE_SORT
    printf("\n");
#endif
}