skip to content

JavaScript: DHTML Bubble Sort

 Tweet Share0 Tweets

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.

idcolourrandom
1yellow114
2orange687
3red649
4orange866
5orange238
6orange849
7yellow46
8orange268
9green860
10orange172
11purple84
12red743
13purple778
14red876
15red849
16orange319
17blue179
18blue783
19red519
20orange682
Sort by DESC?

[add rows to TABLE]

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 that doesn't sound like good programming practice to you then you probably want to look at the OOP version)

// 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, if 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).

Note: 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

Send a message to The Art of Web:


used only for us to reply, and to display your gravatar.

<- copy the digits from the image into this box

press <Esc> or click outside this box to close

Post your comment or question
top