/*
  Copyright (C) 2008 Alessandro Bugatti (alessandro.bugatti@istruzione.it)

  This program is free software; you can redistribute it and/or
  modify it under the terms of the GNU General Public License
  as published by the Free Software Foundation; either version 2
  of the License, or (at your option) any later version.

  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
*/

/*! \file
 *  \brief Algoritmo di ordinamento Insertion Sort non adattativo che ordina
 *  un vettore di N interi
 *  \author Alessandro Bugatti
 *
 *  \version 0.1
 *  \date  Creazione   20/09/06
 *  \date  Ultima modifica 19/09/2013
 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 10000

//Vettore da ordinare
int v[N];

//Insertion sort non adattativo
void sort(int a[], int l, int r)
{
    int i,j;
    for (i=l+1;i<=r;i++)
        for (j=i; j>l; j--)
                if (a[j]<a[j-1])
                {
                    int t = a[j];
                    a[j] = a [j-1];
                    a[j-1]=t;
                }
}


int main(int argc, char *argv[])
{
    //Variabili per misurare il tempo impiegato per l'ordinamento
    clock_t start, end;
    double cpu_time_used;
    //Inizializzo il seme del generatore di numeri casuali
    srand(time(NULL));
    //Riempio il vettore di interi casuali
    for (int i=0;i<N;i++) 
        v[i]=rand()*0xFFFF + rand(); //in questo modo il valore arriva fino
                                     // a oltre 4 miliardi
    printf("\nOrdinamento di un vettore di %d elementi in corso ...\n",N);
    //Faccio partire il "cronometro"...
    start = clock();
    //Ordino il vettore
    sort(v,0,N-1);
    //... e qui fermo il "cronometro"
    end = clock();
    //Calcolo il tempo impiegato trasformandolo in secondi
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("\nTempo di CPU utilizzato: %lf secondi\n" , cpu_time_used );
    return 0;
}