/////////////////////////////////////////////////////////////////
//  Sınislausn á Dæmi 5 á Vikublaği 9 í 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);
}


// 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; 
    } 
}


// Helmingunarleit.  Forrit 2.2 úr Algorithms bók, breytt şannig ağ şağ
//  skili fyrsta sætisnúmerinu sem v getur veriğ í
int search(int a[], int v, int l, int r)
{
	while( r >= l ) {
		int m = (l+r)/2;
		if( v == a[m] ) 
			return m;
		if( v < a[m] )
			r = m-1;
		else
			l = m+1;
	}
	return l;
}



// Innsetningarröğun meğ helmingunarleit
//   kallağ á helmingunarleit til ağ finna stağinn sem a[i] færast til
template <class Item>
void insertionH(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++) {
        Item v = a[i];
		int k = search( a, v, l, i-1 );
			// k er sætiğ sem v á ağ fara í - hliğrum a[k..i-1] upp um eitt sæti
		for( int j=i; j>k; j-- )
            a[j] = a[j-1];
        a[k] = v; 
    } 
}


// Ağalforrit sem bır til slembivektor af heiltölum og rağar şeim
int main(int argc, char *argv[])
{
    const int N = 100000;
    int i;
    int *a = new int[N];
    int *b = new int[N];
    clock_t upph, lok;
     
    for(i = 0; i < N; i++) 
        a[i] = b[i] = (32768*rand() + rand()) % N;

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

    cout << "Timi a Innsetningarrodun ur bok: " << double(lok-upph)/CLOCKS_PER_SEC << endl;

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

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

    return 0;
}