JavaScript: DHTML Bubble Sort
This page demonstrates the most simple sorting algorithm - the Bubble Sort. Using DHTML the table below can be sorted by any column in any direction.
Working Demonstration
You can use the controls under the table to change the sort order and to add more rows containing random values.
| id | colour | random |
|---|---|---|
| 1 | red | 709 |
| 2 | purple | 772 |
| 3 | blue | 352 |
| 4 | blue | 386 |
| 5 | green | 532 |
| 6 | red | 69 |
| 7 | blue | 436 |
| 8 | orange | 436 |
| 9 | blue | 20 |
| 10 | red | 312 |
| 11 | yellow | 690 |
| 12 | blue | 400 |
| 13 | red | 167 |
| 14 | red | 102 |
| 15 | purple | 544 |
| 16 | yellow | 452 |
| 17 | orange | 213 |
| 18 | green | 332 |
| 19 | yellow | 663 |
| 20 | blue | 4 |
How does it work?
The basic components of any sorting algorithm are the ability to: get a value; compare values; and exchange items. We have a function for each, but first we need some some global variables:
If this doesn't sound like good programming practice to you then you probably want to look at the OOP version where it's wrapped in an object.
// global variables
var parent = null; // 'parent' node
var items = new Array(); // array of 'child' nodes
var col = 0; // column for sorting
While it's clear that the items in this case are going to be the rows (TR's), it's not so clear what their parent node is. While you might assume that TR's are children to the TABLE, it turns out that - whether you code it or not - there's actually a TBODY node, a childNode to TABLE, that contains the TR's.
<TABLE>
<THEAD>
(header row appears here - optional)
</THEAD>
<TBODY>
(data rows to be sorted appear here)
</TBODY>
</TABLE>
To make sure we have the right parent node, we check that it's nodeName is TBODY, and if not, search for a TBODY element within it. If you have some data in the table that needs to stay on top, just insert a THEAD element around that row or rows.
The arguments to the sorting function are then:
- tableid - an id identifying a TABLE or TBODY element;
- n - identifies which column of the TABLE we want to sort by; and
- desc - a boolean value indicating the direction of the sort.
function sortTable(tableid, n, desc)
{
// parent node identified by id="tableid"
parent = document.getElementById(tableid);
col = n;
// parent node for sorting rows must be TBODY and not TABLE
if(parent.nodeName != "TBODY")
parent = parent.getElementsByTagName("TBODY")[0];
if(parent.nodeName != "TBODY")
return false;
// assert: parent is now a TBODY node
items = parent.getElementsByTagName("TR");
var N = items.length;
// bubble sort - not very efficient but ok for short lists
for(var j=N-1; j > 0; j--) {
for(var i=0; i < j; i++) {
if(compare(get(i+1), get(i), desc)) exchange(i+1, i);
}
}
return true;
}
We don't need to go into the mechanics of the Bubble Sort itself. Suffice to say that it's a mechanical sorting process that's very reliable, but not very efficient.
get, compare and exchange
The get function is relatively straight-forward. It selects the ith row and then the colth table cell. The value for sorting purposes is the value of the first childNode of the TD.
If the value found is numeric then it is returned as a number (an integer to be specific but you could probably handle floats in a similar way).
If the value within the TD is contained in another tag (such as an A or FONT tag) then the function will need to be modified. You can see one solution for this, as well as other enhancements, implemented in the OOP version.
function get(i)
{
var node = items[i].getElementsByTagName("TD")[col];
if(node.childNodes.length == 0) return "";
// assumes firstChild of node is a textNode
var retval = node.firstChild.nodeValue;
if(parseInt(retval) == retval) return parseInt(retval);
return retval;
}
Nothing much to explain for the compare function:
function compare(val1, val2, desc)
{
return (desc) ? val1 > val2 : val1 < val2;
}
The exchange function is nice and compact. We insert one element of the items array before it's predecessor. This automatically removes it from it's previous position (to avoid duplication) resulting in an exchange of adjacent rows.
function exchange(i, j)
{
// exchange adjacent items
parent.insertBefore(items[i], items[j]);
}
That's all there is to it. For more advanced (and complicated) sorting techniques, see the Insertion Sort, Shell Sort and Quick Sort demonstrations. Each one is (in theory) more efficient that the preceding algorithms.
Related Articles - Sorting Algorithms
- JavaScript DHTML Insertion Sort
- JavaScript DHTML Shell Sort
- JavaScript DHTML Quick Sort
- JavaScript DHTML Bubble Sort
- JavaScript Sorting Algorithm Comparison
- JavaScript DHTML Sorting Using OOP - Example 1
- JavaScript DHTML Sorting Algorithms
- PHP Sorting Arrays of Arrays
- PHP Sorting SimpleXMLElement Object arrays