//////////////////////////////////////////////////////////////////////
//   Sýnislausn á Forritunarverkefni 3,  Uppbygging tölva haust 2001
//
//   Hjálmtýr Hafsteinsson, okt. 2001
//////////////////////////////////////////////////////////////////////
#include <iostream.h>
#include <stdlib.h>
#include <time.h>

#define N 2000000


int partition(int a[], int l, int r)
  { int i = l-1, j = r; int v = a[r];

__asm{
		; Nota eingöngu gistu, ekki staðværu breyturnar
		mov	ebx, a
		mov	eax, i
		mov	ecx, j
		mov	edx, v
ytri:	

;         while (a[++i] < v) ;
vinstr:	inc	eax
		cmp	[ebx + eax*4], edx
		jl	vinstr

;        while (v < a[--j]) if (j == l) break;
haegr:	dec ecx
		cmp edx, [ebx + ecx*4]
		jge hut
		cmp ecx, l
		je	hut
		jmp haegr

hut:
;        if (i >= j) break;
		cmp eax, ecx
		jge put

;        exch(a[i], a[j]);
		mov	esi, [ebx + eax*4]
		xchg esi, [ebx + ecx*4]
		mov [ebx + eax*4], esi

		jmp ytri

put:
;    exch(a[i], a[r]);
;		xchg dword ptr [ebx + eax*4], dword ptr [ebx + edx*4]
		mov	esi, [ebx + eax*4]
		mov [ebx + eax*4], edx			; EDX er þegar með a[r] (þ.e. v)
		mov	edx, r
		mov [ebx + edx*4], esi

	}
}


//////////////////////////////////////////////////////////////////////////
////////////////////// Gamla skiptifallið ////////////////////////////////
void exch( int &x, int &y )
{
	int t = x;
	x = y;
	y = t;
}

int partold(int a[], int l, int r)
  { int i = l-1, j = r; int v = a[r];
    for (;;)
      { 
        while (a[++i] < v) ;
        while (v < a[--j]) if (j == l) break;
        if (i >= j) break;
        exch(a[i], a[j]);
      }
    exch(a[i], a[r]);
    return i;
  }
////////////////////// Gamla skiptifallið ////////////////////////////////
//////////////////////////////////////////////////////////////////////////


void quicksort(int a[], int l, int r)
  {
    if (r <= l) return;

//  Til að tímamæla aðferðirnar
//    int i = partold(a, l, r);
    int i = partition(a, l, r);
    quicksort(a, l, i-1);
    quicksort(a, i+1, r);
  }


// Prófunarforrit
void main()
{
	clock_t upph, lok;
	int *a, i;

	a = new int[N];

	for( i=0; i<N; i++ )
		a[i] = 65536*rand() + rand();

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

	lok = clock();

	cout << "Tími: " << double( lok-upph ) / CLOCKS_PER_SEC << endl;

}