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

//------------------------------------------------------
/*
 * Exécute un tri par insertion avec la séparation donnée
 * If gap == 1, on fait un tri ordinaire.
 * If gap >= length, on ne fait rien.
 */
void sort_shell_phase(unsigned int a[],unsigned int length, int gap) {
    int i;
 
    /* puti(gap); */
    for (i = gap; i < length; ++i) {
        unsigned int value = a[i];
        int j;
        for (j = i - gap; j >= 0 && a[j] > value; j -= gap) {
#if VERBOSE_SORT
	    printf("+");
#endif
            a[j + gap] = a[j];
#if VERBOSE_SORT
	    printf("-");
#endif
        }
        a[j + gap] = value;
    }
}
 
void sort_shell(unsigned int *base, unsigned int n) {
    /*
     * gaps[] doit approximer une Série géométrique.
     * La sequence suivante est la meilleure connue en terme
     * de nombre moyen de comparaisons. voir:
     * http://www.research.att.com/~njas/sequences/A102549
     */
    static const int gaps[] = {
        1, 4, 10, 23, 57, 132, 301, 701
    };
    int sizeIndex;
 
    for (sizeIndex = sizeof(gaps)/sizeof(gaps[0]) - 1;
               sizeIndex >= 0;
               --sizeIndex)
        sort_shell_phase(base, n, gaps[sizeIndex]);
#if VERBOSE_SORT
    printf("\n");
#endif
}