/*
  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 Quick Sort 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>

#define N 5000000

int partition(int a[], int l, int r)
{
    int i=l-1, j=r, t;
    int v=a[r];
    for(;;)
    {
        while (a[++i]<v);
        while (v<a[--j]) if (j==l) break;
        if (i>=j) break;
        t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
    t=a[i];
    a[i]=a[r];
    a[r]=t;
    return i;
}

void sort(int a[],int l, int r)
{
    int i;
    if (r<=l) return;
    i=partition(a,l,r);
    sort(a,l,i-1);
    sort(a,i+1,r);
}

int v[N];

int main(int argc, char *argv[])
{

    clock_t start, end;
    double cpu_time_used;
    srand(time(NULL));
    for (int i=0; i<N; i++) v[i]=rand()*0xFFFF + rand();
    printf("\nOrdinamento di un vettore di %d elementi in corso ...",N);
    start = clock();
    //Ordina il vettore
    sort(v,0,N-1);
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("\nTempo di CPU utilizzato: %lf secondi.\n", cpu_time_used) ;
    return 0;
}