skip to content

JavaScript: DHTML Shell Sort

 Tweet Share0 Tweets

JavaScript: DHTML Shell Sort

This page demonstrates the Shell Sort algorithm. This appears to be the most efficient algorithm out of the four presented on this site. That may be because of 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.

idcolourrandom
1yellow225
2purple390
3red385
4yellow204
5green712
6blue644
7purple666
8blue95
9yellow834
10red487
11purple86
12orange128
13yellow817
14purple440
15orange186
16orange354
17purple604
18orange369
19yellow950
20red561
Sort by DESC?

[add rows to TABLE]

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.

< 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