JavaScript: DHTML Shell Sort
This page demonstrates the Shell Sort algorithm which appears to be the most efficient algorithm out of the four presented on this site.
That may be due to faults in the implementation of the Quick Sort algorithm (see related link on that page for details), but until that's confirmed you probably want to use the shell sort.
Working Demonstration
| id | colour | random |
|---|---|---|
| 1 | blue | 376 |
| 2 | orange | 624 |
| 3 | yellow | 580 |
| 4 | yellow | 577 |
| 5 | green | 612 |
| 6 | purple | 41 |
| 7 | green | 98 |
| 8 | blue | 948 |
| 9 | blue | 91 |
| 10 | orange | 370 |
| 11 | purple | 938 |
| 12 | blue | 358 |
| 13 | blue | 161 |
| 14 | red | 586 |
| 15 | yellow | 197 |
| 16 | yellow | 567 |
| 17 | green | 625 |
| 18 | red | 789 |
| 19 | purple | 748 |
| 20 | purple | 130 |
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 col = 0;
var parent = null;
var items = new Array();
var N = 0;
function isort(m, k, desc)
{
for(var j=m+k; j < N; j+= k) {
for(var i=j; i >= k && compare(get(i), get(i-k), desc); i-= k) {
exchange(i, i-k);
}
}
}
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;
items = parent.getElementsByTagName("TR");
N = items.length;
// shell sort
if((k = Math.floor(N/5)) > 7) {
for(var m=0; m < k; m++) isort(m, k, desc);
}
if((k = Math.floor(N/7)) > 7) {
for(var m=0; m < k; m++) isort(m, k, desc);
}
for(k=7; k > 0; k -= 2) {
for(var m=0; m < k; m++) isort(m, k, desc);
}
}
Interestingly, the Shell Sort algorithm actually makes use of the previously presented Insertion Sort algorithm.
New exchange function
Because the Shell Sort algorithm requires non-adjacent items to be swapped, we need to make some changes to the exchange function that was previously used for both the Bubble Sort and Insertion Sort. The get and compare functions remain unchanged.
function exchange(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]);
}
}
}
For an even more advanced sorting technique, see the Quick Sort demonstration.
Related Articles - Sorting Algorithms
- JavaScript DHTML Sorting Algorithms
- JavaScript DHTML Sorting Using OOP - Example 1
- JavaScript DHTML Quick Sort
- JavaScript DHTML Shell Sort
- JavaScript Sorting Algorithm Comparison
- JavaScript DHTML Insertion Sort
- JavaScript DHTML Bubble Sort
- PHP Sorting Arrays of Arrays
- PHP Sorting SimpleXMLElement Object arrays