////////////////////////////////////////////////////////////////////////
//  Sınislausn á Verkefni 2 í Tölvunarfræği 2
//
//  Hjálmtır Hafsteinsson, apríl 2005
////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
using namespace std;


template <class Item> 
inline void exch(Item &A, Item &B) 
{
    Item t = A;
    A = B;
    B = t;
} 

template <class Item> 
inline void compexch(Item &A, Item &B) 
{
    if (B < A) exch(A, B);
}

template <class Item>
void insertion(Item a[], int l, int r)
{
    int i;
    for (i = r; i > l; i--) compexch(a[i-1], a[i]);
    for (i = l+2; i <= r; i++) {
        int j = i; Item v = a[i]; 
        while (v < a[j-1]) {
            a[j] = a[j-1]; j--;
        }
        a[j] = v; 
    } 
}

// Partition fall sem gerir ráğ fyrir varğstökum á báğum endum fylkisins
template <class Item>
inline int partition(Item a[], int l, int r)
{
	register int i = l-1, j = r;
	Item v = a[r];
	for (;;) { 
		while (a[++i] < v) ;
		while (v < a[--j]) ;
		if (i >= j) break;
		exch(a[i], a[j]);
	}
	exch(a[i], a[r]);
	return i;
}

const int M = 15;           // Hvenær skipta á yfir í Innsetningarröğun


// Blönduğ röğun, şar sem Innsetningarröğun er notuğ inní Quicksort til ağ
//  rağa litlum listum (şegar stærğ <= M)
template <class Item>
void quicksorti( Item a[], int l, int r )
{
    if (r-l <= M) {insertion( a, l, r ); return; }
    exch(a[(l+r)/2], a[r-1]);
    compexch(a[l], a[r-1]); 
      compexch(a[l], a[r]); 
        compexch(a[r-1], a[r]);
    int i = partition(a, l+1, r-1);
    quicksorti(a, l, i-1);
    quicksorti(a, i+1, r);
} 



// Samanburğarfall fyrir qsort falliğ
int samanb( const void *a, const void *b )
{
	return ( *(int*)a - *(int*)b ); 
}



// Falliğ fær inn n-staka heiltölufylkiğ a og upphafsstillir şağ şannig ağ
//  şağ sé næstum şví rağağ.  Fjöldi staka sem hefur veriğ færğur til er hf*n
void naerRadad( int a[], int n, double hf )
{
	int fjRugl = n * hf;

	// Búa til stök í röğ...
	for( int i=0; i<n; i++ )
		a[i] = i;

	// Rugla şeim ağeins...
	for( int k=0; k<fjRugl; k++ ) {
		int r1 = (32768*rand() + rand()) % n;
		int r2 = (32768*rand() + rand()) % n;
		exch( a[r1], a[r2] );
	}
}

// Falliğ fær inn n-staka heiltölufylkiğ a og upphafsstillir şağ şannig ağ şağ
//  sé næstum şví rağağ í öfuga röğ.  Fjöldi staka sem hefur veriğ færğur til er hf*n
void naerOfugtRadad( int a[], int n, double hf )
{
	int fjRugl = n * hf;

	// Búa til stök í röğ...
	for( int i=0; i<n; i++ )
		a[i] = n-i;

	// Rugla şeim ağeins...
	for( int k=0; k<fjRugl; k++ ) {
		int r1 = (32768*rand() + rand()) % n;
		int r2 = (32768*rand() + rand()) % n;
		exch( a[r1], a[r2] );
	}
}

// Falliğ fær inn n-staka heiltölufylkiğ a og upphafsstillir şağ şannig ağ şağ
//  inniheldur ağeins k mismunandi gildi sem eru jafndreifğ um fylkiğ
void adeinsKMism( int a[], int n, int k )
{
	for( int i=0; i<n; i++ )
		a[i] = (32768*rand() + rand()) % k;
}




void maelingFalla( int a[], int N )
{
    clock_t upph, lok;
    int *b = new int[N];
    int *c = new int[N];

    // Búa til tvö afrit af inntaksfylkinu
    for( int i=0; i<N; i++ ) 
        b[i] = c[i] = a[i];

	// ---------------  qsort  -----------------
    upph = clock();
    qsort( (void *)a, (size_t)N, sizeof(int), samanb );
    lok = clock();

	for( i=0; i<N-1; i++ )
		if( a[i+1] < a[i] )
			cout << "Ekki radad!";

    cout << "Timi a qsort: " << double(lok-upph)/CLOCKS_PER_SEC << " sek." << endl;

	// ---------------  sort  -----------------
    upph = clock();
    sort( &b[0], &b[N] );
    lok = clock();

	for( i=0; i<N-1; i++ )
		if( b[i+1] < b[i] )
			cout << "Ekki radad!";

    cout << "Timi a sort: " << double(lok-upph)/CLOCKS_PER_SEC << " sek." << endl;

	// ---------------  mín ağferğ  -----------------
    upph = clock();
	quicksorti( c, 0, N-1 );
    lok = clock();

	for( i=0; i<N-1; i++ )
		if( c[i+1] < c[i] )
			cout << "Ekki radad!";

    cout << "Timi a minni adferd: " << double(lok-upph)/CLOCKS_PER_SEC << " sek." << endl;

	// Skila fylkjunum til baka...
	delete[] b;
	delete[] c;
}


// Ağalforrit sem bır til slembivektor og tekur tímann á röğunarağferğunum
int main(int argc, char *argv[])
{
    const int N = 1000000;
    int i;
    int *a = new int[N];

	cout << "===== Tilfelli 1 =====" << endl;
	cout << "  Naestum thvi radad inntak" << endl;
	naerRadad( a, N, 0.0001 );
	maelingFalla( a, N );
	cout << "======================" << endl;

	cout << "===== Tilfelli 2 =====" << endl;
	cout << "  Naestum thvi ofugt radad inntak" << endl;
	naerOfugtRadad( a, N, 0.0001 );
	maelingFalla( a, N );
	cout << "======================" << endl;

	cout << "===== Tilfelli 3 =====" << endl;
	cout << "  Adeins 100 mism. gildi" << endl;
	adeinsKMism( a, N, 100 );
	maelingFalla( a, N );
	cout << "======================" << endl;

	cout << "===== Tilfelli 4 =====" << endl;
	cout << "  Jafndreift inntak" << endl;
	adeinsKMism( a, N, N );
	maelingFalla( a, N );
	cout << "======================" << endl;

	delete[] a;

    return 0;
}