Object Oriented .JS QuickSort - Documentation

This is the documentation for the JavaScript included in the HTML table sorting tutorial.

Before we can get start working with the actual table, we need to initialize the variables inside our TSorter object and add the onclick behaviours to the cells in the table's header row. Caution must be taken when referencing this from inside the onclick handler where this is referring to the cell that is clicked, not TSorter.

Now, on to the code!

initialize the variables and add onclick() states to the table headers

function TSorter(){
	var table = Object;
	var trs = Array;
	var ths = Array;
	var curSortCol = Object;
	var prevSortCol = '3';
	var sortType = Object;

	function get(){}

	function getCell(index){
		return trs[index].cells[curSortCol] 
	}
	
	this.init = function(tableName)
	{
		table = document.getElementById(tableName);
		ths = table.getElementsByTagName("th");
		for(var i = 0; i < ths.length ; i++)
		{
			ths[i].onclick = function()
			{
				sort(this);
			}
		}
		return true;
	};
	...
}
	
function init()
{
	var Table1Sorter = new TSorter;
	Table1Sorter.init('result_table');
}
	
window.onload = init;

Each time sort is called, we must have access to the table rows for comparison. Next is the onclick handlers which we registered above. This function determines the best action to be taken on the table to get it sorted. If the most recent column sorted is the column clicked then there is no sense in calling QuickSort() to flip the table, instead it calls ReverseTable() to get the job done quicker.

onclick() handler for table header cells

function sort(oTH)
{
	curSortCol = oTH.cellIndex;
	sortType = oTH.abbr;
	trs = table.tBodies[0].getElementsByTagName("tr");

	//set the get function
	setGet(sortType)

	// if already sorted just reverse
	if(prevSortCol == curSortCol)
	{
		oTH.className = (oTH.className != 'ascend' ? 'ascend' : 'descend' );
		reverseTable();
	}
	// not sorted - call quicksort
	else
	{
		oTH.className = 'ascend';
		if(ths[prevSortCol].className != 'exc_cell'){ths[prevSortCol].className = '';}
		quicksort(0, trs.length);
	}
	prevSortCol = curSortCol;
}

This is where the object oriented implementation really pays off. Each time we call sort() we are able to specify what function to use to access the content of the table cells. This means that we are no longer limited to simple tables which have only one child textNode. It allows us to enhance the data by providing links, wrapping text in spans with class names, or add images in cells to name a few.

Because this is an unobtrusive script inline event handlers are out. How, then, will we specify which function to use? I chose to match the get function to the id attribute of the table header cell.

A few more sample get() functions and use cases are available.

setGet() - determines which cell value to use for comparison

function setGet(sortType)
{
	switch(sortType)
	{   
		case "link":
			get = function(index)
			{
				return  getCell(index).firstChild.firstChild.nodeValue;
			};
			break;
		case "text_inputs":
			get = function(index)
			{	
				return getCell(index).firstChild.value;
			};
			break;
		case "missing_values":
			get = function(index){	
				var cell = getCell(index);
				if(cell.firstChild)
					return cell.firstChild.nodeValue;
				else
					return ' ';
			}
			break;			
		default:
			get = function(index){	return getCell(index).firstChild.nodeValue;};
			break;
	};	
}

Now we're into the meat of the object. exchange takes two parameters(i and j) which are the indices of the rows which are to be switched. These rows form the input to the native JavaScript function insertBefore(rowToMove, rowToPrepend). For more information on switching two table rows, try this supplemental article.

Exchange two Table Rows

function exchange(i, j)
{
	if(i == j+1) {
		table.tBodies[0].insertBefore(trs[i], trs[j]);
	} else if(j == i+1) {
		table.tBodies[0].insertBefore(trs[j], trs[i]);
	} else {
		var tmpNode = table.tBodies[0].replaceChild(trs[i], trs[j]);
		if(typeof(trs[i]) == "undefined") {
			table.appendChild(tmpNode);
		} else {
			table.tBodies[0].insertBefore(tmpNode, trs[i]);
		}
	}
}

Here we have a refreshing simple, but unmistakably quick Reverse Table Sort. As mentioned above, it is not always necessary to use the full QuickSort function if the table is in the exact opposite order desired. This function starts at row 2 and sequentially inserts the remaining rows into position 1. It is O(n), and that's a good thing.

Reverse Table Row Order

function reverseTable()
{
	for(var i = 1; i<trs.length; i++)
	{
		table.tBodies[0].insertBefore(trs[i], trs[0]);
	}
}

QuickSort [O(nlogn)] is a recursive sorting algorithm originally written by Hoare. I won't go into too much depth on the algorithm itself as there are many sites which define it very well. If you are interested in seeing how well QuickSort stacks up against the competition take a look at these interactive sorting demos.

QuickSort - Divide and Conquer

function quicksort(lo, hi)
{
	if(hi <= lo+1) return;
	 
	if((hi - lo) == 2) {
		if(get(hi-1) > get(lo)) exchange(hi-1, lo);
		return;
	}
	
	var i = lo + 1;
	var j = hi - 1;
	
	if(get(lo) > get(i)) exchange(i, lo);
	if(get(j) > get(lo)) exchange(lo, j);
	if(get(lo) > get(i)) exchange(i, lo);
	
	var pivot = get(lo);
	
	while(true) {
		j--;
		while(pivot > get(j)) j--;
		i++;
		while(get(i) > pivot) i++;
		if(j <= i) break;
		exchange(i, j);
	}
	exchange(lo, j);
	
	if((j-lo) < (hi-j)) {
		quicksort(lo, j);
		quicksort(j+1, hi);
	} else {
		quicksort(j+1, hi);
		quicksort(lo, j);
	}
}