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

  /* Stoperica za Quicksort iz standardne C biblioteke.
     Test na polju od 10^7 slucajno generiranih intova.
  */

    /* Globalno polje x za sortiranje.
       Namjerno je globalno - zato da nema problema s velicinom
       programskog stoga za automatske varijable u funkcijama. */

#define MAXN 10000000    /* 10^7 */

int x[MAXN];

    /* Funkcija za procesorsko vrijeme u sekundama - preko clock(). */

double dsecnd (void) {
    return (double)( clock() ) / CLOCKS_PER_SEC;
}

    /* Brzo generiranje slucajnog broja iz [0, 2^30 - 1].
       KORISTI da je RAND_MAX = 2^15 - 1.
       Dvostruki poziv rand(), uz pomak prvog broja za 15 bitova. */

int randint(void) {
    return ( rand() << 15 ) + rand();
}

    /* Usporedba cijelih brojeva za qsort iz C biblioteke. */

int intcomp(const int *p_a, const int *p_b)
{
  /* Opcenito, NIJE dobro: return *p_a - *p_b;
     jer rezultat ne mora biti korektno prikaziv! */
  /* Medjutim, to RADI za brojeve iz [0, 2^30 - 1],
     dobivene iz randint. */

    if (*p_a < *p_b)
        return -1;
    else if (*p_a > *p_b)
        return 1;
    else
        return 0;
}

  /* Tip funkcije za usporedbu, kod casta u pozivu qsort. */

typedef int (*Comp_fun) (const void*, const void*);


    /* Glavni program. */

int main(void)
{
    int n = MAXN;    /* Broj elemenata u polju. */
    int i;
    double start, stop;

        /* Generiranje slucajnog polja x s n intova. */

    for (i = 0; i < n; ++i)
        x[i] = randint();

        /* Quicksort na polju x, sa stopericom oko poziva. */

    start = dsecnd();
    qsort(x, n, sizeof(int), (Comp_fun) intcomp);
    stop = dsecnd();

        /* Provjera sortiranosti polja x. */

    for (i = 1; i < n; ++i)
        if (x[i-1] > x[i])
            printf(" Greska na [%d, %d]\n", i-1, i);

        /* Ispis vremena. */

    printf(" n = %8d,  vrijeme = %9.3f [s]\n", n, stop - start);

    return 0;
}