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

/*
    Usporedba sort algoritama.
    Kompajlirati s opcijom -O2.
    Podesiti vrijednost od n u main tako da prvi selection sort traje cca 4 sekunde.
*/ 

void selection_sort( int x[], int n )
{
    int i, j;

    for( i = 0; i < n-1; ++i )
        for( j = i+1; j < n; ++j )
            if( x[j] < x[i] )
            {
                int temp = x[i];
                x[i] = x[j];
                x[j] = temp;
            }
}


void selection_sort_brzi( int x[], int n )
{
    int i, j;

    for( i = 0; i < n-1; ++i )
    {
        int mini = x[i], index = i;
        for( j = i+1; j < n; ++j )
            if( x[j] < mini )
            {
                mini = x[j];
                index = j;
            }

        if( i != index )
        {
            int temp = x[i];
            x[i] = x[index];
            x[index] = temp;
        }
    }
}


void bubble_sort( int x[], int n )
{
    int sortiran, i, prolaz;

    sortiran = 0; prolaz = 0;
    while( !sortiran )
    {
        sortiran = 1; ++prolaz;

        for( i = 0; i < n-prolaz; ++i )
            if( x[i+1] < x[i] )
            {
                int temp = x[i];
                x[i] = x[i+1];
                x[i+1] = temp;
            
                sortiran = 0;
            }
    }
}


void insert( int x[], int n, int novi )
{
    // Polje x duljine n je vec sortirano. Ubaci novi element tako da ostane sortirano.
    int i = n-1;
    while( i >= 0 && x[i] > novi )
    {
        x[i+1] = x[i];
        --i;
    }

    // Sada je i=-1 ili je x[i] <= novi.
    x[i+1] = novi;
}


void insertion_sort( int x[], int n )
{
    int i;

    for( i = 1; i < n; ++i )
        insert( x, i, x[i] );
}


void quick_sort( int x[], int n, int lo, int hi )
{
    if( lo < hi )
    {
        int pivot = x[hi], i = lo, j, temp;
        for( j = lo; j < hi; ++j )
            if( x[j] < pivot )
            {
                temp = x[i];
                x[i] = x[j];
                x[j] = temp;

                ++i;
            }

        temp = x[i];
        x[i] = x[hi];
        x[hi] = temp;

        quick_sort(x, n, lo, i-1);
        quick_sort(x, n, i+1, hi);
    }
}


int check( int x[], int sorted[], int n )
{
    int i;
    for( i = 0; i < n; ++i )
        if( x[i] != sorted[i] )
            return 0;

    return 1;
}


clock_t clock_start;

void tic()
{
    clock_start = clock();
}


double toc()
{
    clock_t clock_end = clock();
    return (double)(clock_end - clock_start) / CLOCKS_PER_SEC;
}


int cmp_fun( const void *a, const void *b ) 
{
    return ( *(int*)a - *(int*)b );
}


void test( int n )
{
    int *x, *orig, *sorted;
    double delta;

    // Alociraj memoriju za tri niza duljine n.
    x = (int *) malloc( n * sizeof(int) );
    orig = (int *) malloc( n * sizeof(int) );
    sorted = (int *) malloc( n * sizeof(int) );

    // Generiraj slučajni niz duljine n.
    int i;
    srand( time(0) );
    for( i = 0; i < n; ++i )
        orig[i] = rand();

    // qsort iz standardne biblioteke.
    memcpy( sorted, orig, n * sizeof(int) );
    qsort( sorted, n, sizeof(int), cmp_fun );

    // Selection sort.
    memcpy( x, orig, n * sizeof(int) );
    tic(); selection_sort( x, n ); delta = toc();
    printf( "Selection sort (sort %s)    ... %lfs\n", (check(x, sorted, n) ? "OK" : "NOT OK"), delta );

    // Selection sort ubrzani.
    memcpy( x, orig, n * sizeof(int) );
    tic(); selection_sort_brzi( x, n ); delta = toc();
    printf( "Selection sort v2 (sort %s) ... %lfs\n", (check(x, sorted, n) ? "OK" : "NOT OK"), delta );

    // Bubble sort.
    memcpy( x, orig, n * sizeof(int) );
    tic(); bubble_sort( x, n ); delta = toc();
    printf( "Bubble sort (sort %s)       ... %lfs\n", (check(x, sorted, n) ? "OK" : "NOT OK"), delta );

    // Insertion sort.
    memcpy( x, orig, n * sizeof(int) );
    tic(); insertion_sort( x, n ); delta = toc();
    printf( "Insertion sort (sort %s)    ... %lfs\n", (check(x, sorted, n) ? "OK" : "NOT OK"), delta );

    // Quick sort.
    memcpy( x, orig, n * sizeof(int) );
    tic(); quick_sort( x, n, 0, n-1 ); delta = toc();
    printf( "Quick sort (sort %s)        ... %lfs\n", (check(x, sorted, n) ? "OK" : "NOT OK"), delta );

    // Oslobodi memoriju za nizove.
    free( x );
    free( orig );
    free( sorted );
}


int main( void )
{
    int n;

    // Podesite ovisno o brzini svog racunala tako da prvi sort traje cca 4 sekunde.
    n = 50000; 
    printf( "Sortiramo slucajno generirani niz duljine n=%d...\n", n );
    test( n );

    n = 2*n;
    printf( "\n\nSortiramo slucajno generirani niz duljine n=%d...\n", n );
    test( n );

    return 0;
}