/////////////////////////////////////////////////////////////////
//  Sýnislausn á Dæmi 4 á Vikublaði 10 í Tölvunarfræði 2
//
//  Hjálmtýr Hafsteinsson, mars 2005
/////////////////////////////////////////////////////////////////
#include <iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;

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

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

template <class Item>
Item max(Item A, Item B)
{
	if( A < B ) return B;
	else return A;
}


// Innsetningarröðun, eins og hún er í bókinni (með minnsta stakið sem varðstak)
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; 
    } 
}


void slembiZipf( int c, int n, int a[] )
{
	int k = 1;

	int ci = c;		// Telur niður fjölda eins staka
	int cn = c;		// Fjöldi eins staka á hverjum tíma

	int i = 0;
	while( i < n ) {
		for( ci=0; ci<cn && i<n; ci++, i++ )
			a[i] = k;
		k++;
		cn = max( c/k, 1 );
	}

	// Stokka fylkið a...
	for( i=n-1; i>0; i-- ) {
		int r = (32768*rand() + rand()) % (i+1);
		exch( a[i], a[r] );
	}
}



// Aðalforrit sem býr til slembivektor af heiltölum og raðar þeim
int main(int argc, char *argv[])
{
    const int N = 50000;
    int i;
    int *a = new int[N];
    int *b = new int[N];
    clock_t upph, lok;

	// Upphafsstilla slemibitölugjafa
	srand( (unsigned)time( NULL ) );

	// Búa til jafndreift slembifylki...
    for(i = 0; i < N; i++) 
        a[i] = (32768*rand() + rand()) % N;

	// Búa til Zipf-dreift slembifylki...
	slembiZipf( 3*N/4, N, b );

    upph = clock();
    insertion(a, 0, N-1);
    lok = clock();

    cout << "Timi a Innsetningarrodun med jafndreifdu inntaki: " << double(lok-upph)/CLOCKS_PER_SEC << endl;

    upph = clock();
    insertion(b, 0, N-1);
    lok = clock();

    cout << "Timi a Innsetningarrodun med Zipf-dreifdu inntaki: " << double(lok-upph)/CLOCKS_PER_SEC << endl;

    return 0;
}