/***********************************************************
This function adapted from the algorithm given in:
Data Abstractions & Structures Using C++, by
Mark Headington and David Riley, pg. 586.
Quicksort is the fastest array sorting routine for
unordered arrays.  Its big O is n log n.
**************************************************************/
function Quicksort(vec, loBound, hiBound){
	var pivot, loSwap, hiSwap, temp;
	/* Two items to sort*/
	if (hiBound - loBound == 1){
		if (vec[loBound].position > vec[hiBound].position){
			temp = vec[loBound];
			vec[loBound] = vec[hiBound];
			vec[hiBound] = temp;
		}
		return;
	}
	/* Three or more items to sort*/
	pivot = vec[parseInt((loBound + hiBound) / 2)];
	vec[parseInt((loBound + hiBound) / 2)] = vec[loBound];
	vec[loBound] = pivot;
	loSwap = loBound + 1;
	hiSwap = hiBound;
	do {
		/* Find the right loSwap*/
		while (loSwap <= hiSwap && vec[loSwap].position <= pivot.position){
			loSwap++;
		}
		/* Find the right hiSwap*/
		while (vec[hiSwap].position > pivot.position){
			hiSwap--;
		}
		/* Swap values if loSwap is less than hiSwap*/
		if (loSwap < hiSwap){
			temp = vec[loSwap];
			vec[loSwap] = vec[hiSwap];
			vec[hiSwap] = temp;
		}
	} while (loSwap < hiSwap)
	vec[loBound] = vec[hiSwap];
	vec[hiSwap] = pivot;
	/* Recursively call function...  the beauty of quicksort*/
	/*2 or more items in first section*/
	if (loBound < hiSwap - 1){
		Quicksort(vec, loBound, hiSwap - 1);
	}
	/* 2 or more items in second section*/
	if (hiSwap + 1 < hiBound){
		Quicksort(vec, hiSwap + 1, hiBound);
	}
}
/**************************************************************
Simply print out an array from the lo bound to the
hi bound.
**************************************************************/
/*
function PrintArray(vec,lo,hi){
	var i;
	for (i = lo; i <= hi; i++){
		document.write(vec[i].position + "<BR>");
	}
}

// Create an array and stuff some values in it
var x = new Array(10);
x[0] = {position:10};
x[1] = {position:-1};
x[2] = {position:3};
x[3] = {position:8};
x[4] = {position:2};
x[5] = {position:11};
x[6] = {position:-4};
x[7] = {position:22};
x[8] = {position:12};
x[9] = {position:6};

document.write("Here is a jumbled array:<BR>");
PrintArray(x,0,9);

//Quicksort(x,0,x.length-1);
Quicksort(x,0,9);
document.write("<BR>Now the array is sorted!<BR>");
PrintArray(x,0,9);
*/