skip to content

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
1blue221
2red344
3green811
4purple813
5orange966
6orange815
7red691
8yellow629
9purple284
10orange704
11orange127
12red822
13red701
14orange117
15blue819
16orange417
17yellow987
18purple248
19purple676
20purple441

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:

  1. tableid - an id identifying a TABLE or TBODY element;
  2. n - identifies which column of the TABLE we want to sort by; and
  3. 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.

< JavaScript

Post your comment or question
top