[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

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

Posted on 2006-04-27
6
Medium Priority
?
1,924 Views
Last Modified: 2012-05-05
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));      
                }
0
Comment
Question by:noamattd
  • 3
  • 2
6 Comments
 
LVL 11

Expert Comment

by:Isisagate
ID: 16555118
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
 
LVL 4

Author Comment

by:noamattd
ID: 16563081
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
 
LVL 5

Accepted Solution

by:
maclema earned 1600 total points
ID: 16565471
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
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
LVL 4

Author Comment

by:noamattd
ID: 16569065
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
 
LVL 5

Expert Comment

by:maclema
ID: 16574922
Good to hear it is working for you :)
0
 
LVL 4

Author Comment

by:noamattd
ID: 16576738
Worked like a charm, thanks a bunch.
0

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This article discusses the difference between strict equality operator and equality operator in JavaScript. The Need: Because JavaScript performs an implicit type conversion when performing comparisons, we have to take this into account when wri…
In this blog, we’ll look at how improvements to Percona XtraDB Cluster improved IST performance.
The viewer will learn the basics of jQuery, including how to invoke it on a web page. Reference your jQuery libraries: (CODE) Include your new external js/jQuery file: (CODE) Write your first lines of code to setup your site for jQuery.: (CODE)
The viewer will learn the basics of jQuery including how to code hide show and toggles. Reference your jQuery libraries: (CODE) Include your new external js/jQuery file: (CODE) Write your first lines of code to setup your site for jQuery…
Suggested Courses

872 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question