Fastest way to sort an unordered list's li elements / child nodes

I have a set of two lists with buttons to move items to and from each list.  The element tree for each list looks like this:

<div>
  <ul>
    <li>
      <label><input checkbox></label>
    </li>
  </ul>
</div>

My method for moving the elements works fine, but the problem is I also need to sort them after each transfer (The contents are strings).

Currently I do this by copying the UL's childNodes into a new array, sorting that array, deleting all nodes from the UL's childnodes, and copying the new ones in from the sorted clone array.  This gets really slow with high numbers of elements (around 1000).

Basically I'd like suggestions or links to better algorithms for doing this.

Here's my sorting code, performed after items are transferred from one list to the other.  dstObj is the UL that items were transferred to.

                var x = new Array();
      for(var j = 0; j < dstObj.childNodes.length; j++)
      {
           x[x.length] = dstObj.childNodes[j];
      }
      x.sort(itemOrder);
      
      while(dstObj.childNodes.length > 0) dstObj.removeChild(dstObj.childNodes[0]);
      
      for(var k = 0; k < x.length; k++)
      {
            dstObj.appendChild(x[k]);      
      }

      function itemOrder(a, b)     //Sort function,
      {
           var aUp = a.innerText.toUpperCase();
           var bUp = b.innerText.toUpperCase();
                     return ( aUp == bUp ? 0 : (aUp < bUp ? -1 : 1));      
                }
LVL 4
noamattdAsked:
Who is Participating?
 
maclemaCommented:
Heres the fasest way I know of.

Times in seconds...

Sorting 1000 Items:
  IE: 1.312
  FF: 1.109

Heres the test page with html and javascript:
-----------------------------------------------------------

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
<title>Untitled Document</title>
<script type="text/javascript">
function randomString()
{
      var r = Math.floor(Math.random()*99999) + "";
      var chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
      var str = "";
      
      for ( var i=0; i<r.length; i++ )
      {
            var n = r.charAt(i);
            str += chars.charAt(n);
      }
      
      return str;
}

function generateList(numOfElems)
{
      var list = document.getElementById("theList");
      i = numOfElems;
      do
      {
            var e = document.createElement("li");
            e.innerHTML = randomString();
            list.appendChild(e);
      }while(i--)
}

//determines how to get the object innerText property
var useInnerText = true;

function init()
{
      generateList(1000);
      
      //determine how to access innerText
      var objTest = document.createElement("li");
      objTest.innerHTML = "A";
      useInnerText = (objTest.innerText) ? true : false;
}
window.onload = init;


//sorting methods
function sortDomList(listID)
{
      var now = new Date();
      var start = now.getTime();
      
      var arr = new Array();
      var list = document.getElementById(listID);
      var i = list.childNodes.length-1;
      do
      {
            var listItem = list.childNodes[i];
            arr.push(listItem);
            list.removeChild(listItem); //remove as we go along
      }
      while(i--)
      arr.sort(itemOrder);
      
      var len = arr.length-1;
      i = arr.length-1;
      do
      {
            list.appendChild(arr[len-i]);
      }
      while(i--)
      
      arr = null; //free up memory
      
      now = new Date();
      var end = now.getTime();
      alert((end-start)/1000);
}

function itemOrder(a, b)     //Sort function,
{
      var aUp, bUp;
      if ( useInnerText == true )
      {
            aUp = a.innerText.toUpperCase();
            bUp = b.innerText.toUpperCase();
      }
      else
      {
            aUp = a.textContent.toUpperCase();
            bUp = b.textContent.toUpperCase();
      }
      return ( aUp == bUp ? 0 : (aUp < bUp ? -1 : 1));    
}
</script>
</head>

<body>
<input name="cmdSort" type="button" value="Sort Now!" onclick="sortDomList('theList');" />
<ul id="theList">
</ul>
</body>
</html>
0
 
IsisagateCommented:
your best bet is probably to put the item into place from the start. So for instance loop through in a for statement the node list you are looking at and find the position in the array where the next element is > then the one you are putting in
then use the

node.insertBefore(); function and insert the new node where it should go. If a position isn't have it add the node to the bottom of the list. This will reduce the overall operations and copying etc.
0
 
noamattdAuthor Commented:
Okay, I dig what you're saying.  Can you give me some sample code?  If possible I'd like to find the insertion point via binary search since, as I said, these are large lists.
0
Ultimate Tool Kit for Technology Solution Provider

Broken down into practical pointers and step-by-step instructions, the IT Service Excellence Tool Kit delivers expert advice for technology solution providers. Get your free copy now.

 
noamattdAuthor Commented:
maclema,

Looks good and your sample code performed about as well as you described.  I'll try implementing it in my app on Monday and if it works out well I'll give you the points.
0
 
maclemaCommented:
Good to hear it is working for you :)
0
 
noamattdAuthor Commented:
Worked like a charm, thanks a bunch.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.