building menu...

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.

id	colour	random
1	purple	145
2	red	147
3	blue	478
4	red	703
5	orange	877
6	green	992
7	green	787
8	green	944
9	purple	550
10	yellow	922
11	blue	522
12	green	283
13	orange	834
14	green	673
15	blue	841
16	blue	535
17	red	770
18	purple	291
19	red	408
20	yellow	420

[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.

DHTML Sorting Using OOP [JAVASCRIPT]
DHTML Quick Sort [JAVASCRIPT]
DHTML Sorting Using OOP - Example 1 [JAVASCRIPT]
DHTML Bubble Sort [JAVASCRIPT]
DHTML Insertion Sort [JAVASCRIPT]
DHTML Shell Sort [JAVASCRIPT]
Sorting Arrays of Arrays [PHP]
Sorting SimpleXMLElement Object arrays [PHP]

< JavaScript

Send a message to The Art of Web:

press <Esc> or click outside this box to close

Post your comment or question

JavaScript: DHTML Shell Sort

JavaScript: DHTML Shell Sort

How does it work?

New exchange function

Related Articles - Sorting Algorithms

Send a message to The Art of Web: