JavaScript: DHTML Insertion Sort
This page demonstrates the Insertion Sort algorithm by applying it to the below HTML table - sorting rows by the values in each column.
Working Demonstration
Use the controls under the table to apply different sort orders. The script will rearrange the rows (too quick to be seen) according to the insertion sort algorithm which involves repeated movements.
| id | colour | random |
|---|---|---|
| 1 | blue | 545 |
| 2 | orange | 702 |
| 3 | yellow | 779 |
| 4 | purple | 588 |
| 5 | yellow | 927 |
| 6 | yellow | 101 |
| 7 | orange | 604 |
| 8 | red | 427 |
| 9 | green | 926 |
| 10 | red | 767 |
| 11 | yellow | 913 |
| 12 | blue | 490 |
| 13 | orange | 292 |
| 14 | green | 266 |
| 15 | blue | 943 |
| 16 | green | 769 |
| 17 | orange | 79 |
| 18 | purple | 516 |
| 19 | red | 628 |
| 20 | yellow | 297 |
How does it work?
For a more detailed discussion on the sorting process, you can refer to the Bubble Sort page. The only difference between the two is the actual sorting algorithm, with the Insertion Sort, in theory, being a little bit faster:
/* global variables */
var parent = null; /* parent node */
var items = new Array(); /* array of 'child' nodes */
var col = 0; /* column for sorting */
function sortTable(tableid, n, desc)
{
parent = document.getElementById(tableid);
col = n;
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;
/* insertion sort */
for(var j=1; j < N; j++) {
for(var i=j; i > 0 && compare(get(i), get(i-1), desc); i--) {
exchange(i, i-1);
}
}
}
The compare, get and exchange functions are common to all the different sorting algorithm implementations and can be found documented here.
For more advanced (and complicated) sorting techniques, see the Shell Sort and Quick Sort demonstrations.
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