JavaScript: DHTML Sorting Algorithms
The article builds on our previous articles presenting functions for sorting HTML tabular data using the Bubble Sort, Insertion Sort, Shell Sort and Quick Sort algorithms. Each algorithm is discussed in more detail there.
Now by using Object-Oriented Programming we can remove the bulk of the code to an external JavaScript file that can be re-used on any page or website. The source code for four self-contained sorting classes can be found below.
Sorting Tabular Data
The HTML TABLE below demonstrates the dynamic sorting of a multi-column table using an OOP version of our previously presented Bubble Sort code. You can just click on the headings or use the controls below to change the sort order.
| id | colour | random |
|---|---|---|
| 1 | orange | 32.96 |
| 2 | red | 84.47 |
| 3 | blue | 54.91 |
| 4 | purple | 86.91 |
| 5 | orange | 75.22 |
| 6 | blue | 71.01 |
| 7 | purple | 84.75 |
| 8 | red | 87.92 |
| 9 | purple | 60.21 |
| 10 | blue | 8.83 |
| 11 | blue | 68.54 |
| 12 | blue | 77.91 |
| 13 | purple | 96.41 |
| 14 | green | 2.49 |
| 15 | orange | 72.91 |
| 16 | purple | 59.71 |
| 17 | green | 39.08 |
| 18 | yellow | 21.98 |
| 19 | yellow | 22.51 |
| 20 | yellow | 29.82 |
JavaScript Source Code
We first need to include the external JavaScript file. By this approach we make the code much more manageable and re-usable. We're also able now to work on the sort functionality without affecting any HTML or inline JavaScript code.
Normally you would include an external JavaScript file using a script tag toward the bottom of your page. Here are the relevant files:
bubblesort.js source code:
var bubbleSort = function(parent, childName, colName) {
// Original JavaScript code by Chirp Internet: www.chirpinternet.eu
// Please acknowledge use of this code by including this header.
/* build array of 'child' nodes */
var items = parent.getElementsByTagName(childName);
var N = items.length;
/* define private methods */
var get = function(i, col, wrapper) {
var retval = null;
var node = null;
if(colName) {
/* sort by col'th element of i'th child */
node = items[i].getElementsByTagName(colName)[col];
} else {
/* sort by i'th child */
node = items[i];
}
if("sort" in node.dataset) {
/* use 'data-sort' attribute */
retval = node.dataset.sort;
} else if(node.childNodes.length > 0) {
if(wrapper) {
/* sort by contents of first 'wrapper' element in 'child' */
retval = node.getElementsByTagName(wrapper)[0].firstChild.nodeValue;
} else {
/* sort by 'child' contents */
retval = node.firstChild.nodeValue;
}
} else {
return "";
}
if(parseFloat(retval) == retval) {
return parseFloat(retval);
}
return retval;
};
var compare = function(val1, val2, desc) {
return (desc) ? val1 > val2 : val1 < val2;
};
var exchange = function(i, j) {
parent.insertBefore(items[i], items[j]);
};
/* define public method */
this.sort = function(col, desc, wrapper) {
for(var j=N-1; j > 0; j--) {
for(var i=0; i < j; i++) {
if(compare(get(i+1, col, wrapper), get(i, col, wrapper), desc)) {
exchange(i+1, i);
}
}
}
};
};
insertionsort.js source code:
var insertionSort = function(parent, childName, colName) {
// Original JavaScript code by Chirp Internet: www.chirpinternet.eu
// Please acknowledge use of this code by including this header.
/* build array of 'child' nodes */
var items = parent.getElementsByTagName(childName);
var N = items.length;
/* define private methods */
var get = function(i, col, wrapper) {
var retval = null;
var node = null;
if(colName) {
/* sort by col'th element of i'th child */
node = items[i].getElementsByTagName(colName)[col];
} else {
/* sort by i'th child */
node = items[i];
}
if("sort" in node.dataset) {
/* use 'data-sort' attribute */
retval = node.dataset.sort;
} else if(node.childNodes.length > 0) {
if(wrapper) {
/* sort by contents of first 'wrapper' element in 'child' */
retval = node.getElementsByTagName(wrapper)[0].firstChild.nodeValue;
} else {
/* sort by 'child' contents */
retval = node.firstChild.nodeValue;
}
} else {
return "";
}
if(parseFloat(retval) == retval) {
return parseFloat(retval);
}
return retval;
};
var compare = function(val1, val2, desc) {
return (desc) ? val1 > val2 : val1 < val2;
};
var exchange = function(i, j) {
parent.insertBefore(items[i], items[j]);
};
/* define public method */
this.sort = function(col, desc, wrapper) {
for(var j=1; j < N; j++) {
for(var i=j; i > 0 && compare(get(i, col, wrapper), get(i-1, col, wrapper), desc); i--) {
exchange(i, i-1);
}
}
};
};
shellsort.js source code:
var shellSort = function(parent, childName, colName) {
// Original JavaScript code by Chirp Internet: www.chirpinternet.eu
// Please acknowledge use of this code by including this header.
/* build array of 'child' nodes */
var items = parent.getElementsByTagName(childName);
var N = items.length;
/* define private methods */
var get = function(i, col, wrapper) {
var retval = null;
var node = null;
if(colName) {
/* sort by col'th element of i'th child */
node = items[i].getElementsByTagName(colName)[col];
} else {
/* sort by i'th child */
node = items[i];
}
if("sort" in node.dataset) {
/* use 'data-sort' attribute */
retval = node.dataset.sort;
} else if(node.childNodes.length > 0) {
if(wrapper) {
/* sort by contents of first 'wrapper' element in 'child' */
retval = node.getElementsByTagName(wrapper)[0].firstChild.nodeValue;
} else {
/* sort by 'child' contents */
retval = node.firstChild.nodeValue;
}
} else {
return "";
}
if(parseFloat(retval) == retval) {
return parseFloat(retval);
}
return retval;
};
var compare = function(val1, val2, desc) {
return (desc) ? val1 > val2 : val1 < val2;
};
var exchange = function(i, j) {
if(i == j+1) {
parent.insertBefore(items[i], items[j]);
} else if(j == i+1) {
parent.insertBefore(items[j], items[i]);
} else {
var tmpNode = parent.replaceChild(items[i], items[j]);
if(typeof(items[i]) == "undefined") {
parent.appendChild(tmpNode);
} else {
parent.insertBefore(tmpNode, items[i]);
}
}
};
var isort = function(m, k, col, desc, wrapper) {
for(let j=m+k; j < N; j+= k) {
for(let i=j; i >= k && compare(get(i, col, wrapper), get(i-k, col, wrapper), desc); i -= k) {
exchange(i, i-k);
}
}
};
/* define public method */
this.sort = function(col, desc, wrapper) {
var k;
if(N > 200) {
if(!confirm("Warning: you are sorting more than 200 items!\nThis may overload your browser.\nDo you want to continue?")) return;
}
if((k = Math.floor(N/5)) > 7) {
for(let m=0; m < k; m++) isort(m, k, col, desc, wrapper);
}
if((k = Math.floor(N/7)) > 7) {
for(let m=0; m < k; m++) isort(m, k, col, desc, wrapper);
}
for(k=7; k > 0; k -= 2) {
for(let m=0; m < k; m++) isort(m, k, col, desc, wrapper);
}
};
};
quicksort.js source code:
var quickSort = function(parent, childName, colName) {
// Original JavaScript code by Chirp Internet: www.chirpinternet.eu
// Please acknowledge use of this code by including this header.
/* build array of 'child' nodes */
var items = parent.getElementsByTagName(childName);
var N = items.length;
/* define private methods */
var get = function(i, col, wrapper) {
var retval = null;
var node = null;
if(colName) {
/* sort by col'th element of i'th child */
node = items[i].getElementsByTagName(colName)[col];
} else {
/* sort by i'th child */
node = items[i];
}
if("sort" in node.dataset) {
/* use 'data-sort' attribute */
retval = node.dataset.sort;
} else if(node.childNodes.length > 0) {
if(wrapper) {
/* sort by contents of first 'wrapper' element in 'child' */
retval = node.getElementsByTagName(wrapper)[0].firstChild.nodeValue;
} else {
/* sort by 'child' contents */
retval = node.firstChild.nodeValue;
}
} else {
return "";
}
if(parseFloat(retval) == retval) {
return parseFloat(retval);
}
return retval;
};
var compare = function(val1, val2, desc) {
return (desc) ? val1 > val2 : val1 < val2;
};
var exchange = function(i, j) {
if(i == j+1) {
parent.insertBefore(items[i], items[j]);
} else if(j == i+1) {
parent.insertBefore(items[j], items[i]);
} else {
var tmpNode = parent.replaceChild(items[i], items[j]);
if(typeof(items[i]) == "undefined") {
parent.appendChild(tmpNode);
} else {
parent.insertBefore(tmpNode, items[i]);
}
}
};
var quicksort = function(m, n, col, desc, wrapper) {
if(n <= m+1) return;
if((n - m) == 2) {
if(compare(get(n-1, col, wrapper), get(m, col, wrapper), desc)) exchange(n-1, m);
return;
}
i = m + 1;
j = n - 1;
if(compare(get(m, col, wrapper), get(i, col, wrapper), desc)) exchange(i, m);
if(compare(get(j, col, wrapper), get(m, col, wrapper), desc)) exchange(m, j);
if(compare(get(m, col, wrapper), get(i, col, wrapper), desc)) exchange(i, m);
pivot = get(m, col, wrapper);
while(true) {
j--;
while(compare(pivot, get(j, col, wrapper), desc)) j--;
i++;
while(compare(get(i, col, wrapper), pivot, desc)) i++;
if(j <= i) break;
exchange(i, j);
}
exchange(m, j);
if((j-m) < (n-j)) {
quicksort(m, j, col, desc, wrapper);
quicksort(j+1, n, col, desc, wrapper);
} else {
quicksort(j+1, n, col, desc, wrapper);
quicksort(m, j, col, desc, wrapper);
}
};
/* define public method */
this.sort = function(col, desc, wrapper) {
quicksort(0, N, col, desc, wrapper);
};
};
The differences between these classes can be seen at the bottom of the class definition where the sorting takes place. The preceding helper functions are identical and could probably be relocated to a separate abstract class.
Remember that only need to include the JavaScript file for one sorting algorithm and you can then use that algorithm anywhere on the page.
If you want to see a visualizatoin of the various sorting algorithms running concurrently, check out this new article where the sorting steps have been slowed down to make them visible.
HTML Source Code
In the sample HTML code below we include the relevant source file from above and then instantiate a new *Sort object and link it to our data table (#data):
<table id="data">
<thead>
<tr>
<th>... header fields ...</th>
</tr>
</thead>
<tbody>
<tr>
<td>... data fields ...</td>
</tr>
</tbody>
</table>
<script src="bubblesort.js"></script>
<script>
var dataTable = document.querySelector("#data");
if(dataTable.nodeName == "TABLE") {
/* parent node for sorting rows must be TBODY and not TABLE */
dataTable = dataTable.querySelector("TBODY");
}
var myTable = new bubbleSort(dataTable, "TR", "TD");
</script>
The three parameters required are:
- the id of the parent node;
- the nodeName of the child nodes (in this case the table rows: TR); and
- the nodeName of the columns (the table cells: TD).
This code can be placed either inline in the body of the page after the TABLE has been defined or elsewhere as a function called by the onLoad (or window.onload or DOMContentLoaded) event.
It cannot for obvious reasons appear before the HTML defining the TABLE has been loaded into the page.
Actually sorting our TABLE is then very simple. We set up a series of onclick or click event listeners and use them to trigger the sorting. For example:
/* sort by the first column ascending */
myTable.sort(0, false);
/* sort by the second column descending */
myTable.sort(1, true);
As demonstrated above the sort command can be triggered by links, forms, buttons or other events.
The sorting takes place within the DOM itself by rearranging the selected elements until they are in the correct order. At normal speeds this process appears to be instantaneous, but can actually involve hundreds or thousands of separate steps.
A common mistake is to forget to wrap your column headers in a THEAD tag. A TBODY tag should also be present, but most (or all) browsers will insert it automatically. See the W3C specification Tables in HTML documents for more information.
Advanced Functionality
If you compare the code in the included file with that presented for the non-OOP Bubble Sort demonstration, you'll see a few new, and hopefully useful, features.
Defining your own sort values
One improvement is that the sort can be applied not just to a TABLE, but to lists and other grouped elements. More on that further down the page.
Another feature is the ability to provide your own 'sort values'. For example, if you wanted to sort by something more complicated than a number or string, such as date values, the results could be less than helpful.
Consider the following demonstration:
| name | dob | dob with sort value | Drew | 22/2/1975 | 22 February 1975 |
|---|---|---|
| Eliza | 30/12/1980 | 30 December 1980 |
| Hermann | 12/7/1972 | 12 July 1972 |
| Alice | 4/2/1948 | 4 February 1948 |
| Bob | 5/10/1954 | 5 October 1954 |
Clicking on name will sort by name, clicking again will reverse the sort - no problem here. Clicking on dob however will sort as if the dates were strings resulting in an alphabetical/numeric sort - not what we wanted.
In the third column (if you look at the HTML) there's an extra data attribute on the TD elements that is picked up during the sort process and used instead of the actual cell (node) values to 'force' a correct sort.
To illustrate this, the first row is actually marked up as:
<tr>
<td>Drew</td>
<td>22/2/1975</td>
<td data-sort="19750222">22 February 1975</td>
</tr>
So all of a sudden you're not limited in cases where the way the data is sorted conflicts with how you want it displayed!
Sorting on a subset of the data
Another new feature is the ability to sort on the contents of a childNode of the 'child' nodes. For example, if a column of your TABLE contains links rather than text you probably want to sort based on the text inside the link.
The table below demonstrates both the problem and the solution:
| # | string | link | wrapper |
|---|---|---|---|
| 1 | Bubble Sort | Bubble Sort | Bubble Sort |
| 2 | Insertion Sort | Insertion Sort | Insertion Sort |
| 3 | Shell Sort | Shell Sort | Shell Sort |
| 4 | Quick Sort | Quick Sort | Quick Sort |
The first two column contain 'plain text' so there's no difficulty in sorting them. The third column introduces a link which causess our script immediately to fail. The reason for this is that it's looking for a 'text' node' wheras those cells actually contain their own 'A' nodes which then contain the text to be sorted.
The code that we would normally use for sorting the third column (which obviously doesn't work) is:
myTable.sort(2, 0);
The way to implement a sort on data that is contained within another tag is used for the last column of the above table:
myTable.sort(3, 0, "a");
The additional parameter tells the sort program to use the contents of the first 'a' tag within the cell rather than just the contents of the cell.
With careful use of this parameter you should be able to sort even the most complicated data. For example, you could insert 'dummy' tags such as <span> into the data to indicate which part of it to use for sorting, and pass 'span' as the extra parameter. Or you can just include your own data-sort values as described above.
Sorting Lists
Here we demonstrate the dynamic sorting of a simple un-ordered list (UL) using an the same Bubble Sort code as for the TABLE demonstration above. All that changes is the way the class is called.
- 46.47
- 0.21
- 90.01
- 2.81
- 42.82
- 45.25
- 15.39
- 47.32
- 37.55
- 83.76
- 48.23
- 16.86
- 56.57
- 61.24
- 75.55
- 34.25
- 84.11
- 25.47
- 98.86
- 13
JavaScript Source Code:
Create a new shellSort object based on the list defined by id="data":
<script src="shellsort.js"></script>
<script>
/* initialise object for sorting */
var myList = document.querySelector("#data");
var sortableList = new shellSort(myList, "LI", "");
</script>
Actually sorting the list is again very simple:
sortableList.sort(0, false); /* sort ascending */
sortableList.sort(0, true); /* sort descending */
This code fails when the list to be sorted also contains one or more child- or sub-lists. The fix would be to check that the items to be sorted have the correct 'parent' node.
Other OOP Sorting Algorithms
Each of the following files contains the functionality of one of the previously presented sorting algorithms. To use them in place of the Bubble Sort, all that is needed is to change the external JavaScript link and the instantiation.
i.e. instead of "new bubbleSort(...)" you would use "new insertionSort(...)", and so forth...
Here are the JavaScript files for all four sorting algorithms:
- DHTML Bubble Sort - OOP (JavaScript file)
- DHTML Insertion Sort - OOP (JavaScript file)
- DHTML Shell Sort - OOP (JavaScript file)
- DHTML Quick Sort - OOP (JavaScript file)
For small datasets there is really not much difference. The Bubble Sort and Insertion Sorts are by far the simplest and most reliable, but very inefficient for large datasets.
The Shell Sort and Quick Sort are much faster but may not work in older browsers (Opera 7 and the Mac version of MSIE 5 for example).
For the type of data typically presented on the web the Shell Sort seems to be the most effective.
Related Articles - Sorting Algorithms
- JavaScript DHTML Insertion Sort
- JavaScript DHTML Quick Sort
- JavaScript DHTML Bubble Sort
- JavaScript DHTML Shell 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
Ben Huffman 12 June, 2008
I just wanted to say that I really appreciated the work you put in on the different sorting algorithms. I started playing with different options for visualizing the algorithms from this site and I though you might be interested in the result.
funkycss.s3.amazonaws.com/bubble-sort-panorama.html
Cheers, and thanks again.
That's fantastic! And great mountain panoramas as well