Solved

Sorting Javascript Array using the QuickSort Algorithm

Posted on 2009-04-01
7
1,183 Views
Last Modified: 2012-05-06
I have the following javascript code which sorts <tr> elements within a <tbody> container.
As I have a large number of <tr> elements to sort, I am wondering if the quick sort method would be appopriate, if anyone can translate the code I have.
The wikipedia reference to Quicksort is here http://en.wikipedia.org/wiki/Quicksort

var trTagsArray = new Array();

 

function initTBody(tdBodyID){

  var tbodytag = document.getElementById(tdBodyID);

  var tbodytagChilds = tbodytag.childNodes

  var i = 0;

  for (i=0;i<tbodytagChilds.length;i++){

    if (tbodytagChilds[i].nodeName == "TR"){

      trTagsArray.push(tbodytagChilds[i]);

    }

  }

}

 

function reOrder(tbodyid,o1,o2,o3){

  var tbodytag = document.getElementById(tbodyid);

  var tbodytagChilds = tbodytag.childNodes;

  var splicedTrTag;

  var oValue;

  var i = 0;

  var smallestSortValue = "ZZZZZZZZZZ";

  var smallestIndex;

  var tempArray = new Array().concat(trTagsArray);

  var tempArray2 = new Array();

  var sortValue="";

  while (tbodytagChilds.length > 0){

    tbodytag.removeChild(tbodytagChilds[0]);

  }

    for (var k=3;k>=1;k--){

    oValue = eval("o" + k);

    while (tempArray.length > 0){

      smallestSortValue = "ZZZZZZZZZZ";

      for (i=0;i<tempArray.length;i++){

        sortValue = getSortValue(tempArray[i],oValue);

        if (sortValue < smallestSortValue){

          smallestSortValue = sortValue;

          smallestIndex = i;

        }

      }

      splicedTrTag = tempArray[smallestIndex];

      tbodytag.appendChild(splicedTrTag);

      tempArray.splice(smallestIndex,1);

      tempArray2.push(splicedTrTag);

    }  

    

    tempArray = new Array().concat(tempArray2);

    tempArray2 = new Array();

  }

 

}

 

function getSortValue(trTag,tagIndex){

  var trTagChilds = trTag.childNodes;

  var indexedTdTag;

  var numTdTag = 0;

  var j=0;

  var returnValue = "";

  for (j=0;j<trTagChilds.length;j++){

    if (trTagChilds[j].nodeName == "TD"){

      ++numTdTag;

      if (tagIndex == numTdTag){

        indexedTdTag = trTagChilds[j];

        break;

      }

    }

  }

  

  try{

    returnValue = indexedTdTag.attributes['sortvalue'].value;

  }catch(err){

    returnValue = "";

  }

  

  return returnValue;

}

Open in new window

0
Comment
Question by:mildurait
  • 4
  • 3
7 Comments
 
LVL 15

Expert Comment

by:fsze88
ID: 24041653
mildurait,
I have tried to solve it out...
But... I facing several problems
1) pass arrays to the function Quicksort Recursively
2) threading problem, I can't wait until first job was finished then fire another one ....
Sorry, I am not Jesus !

<table>

     <tr>

          <td onclick="reOrder('myTBody',1,0,0);">ID</td>

          <td onclick="reOrder('myTBody',2,3,1);">Name</td>

          <td onclick="reOrder('myTBody',3,2,1);">DOB</td></tr>

     </tr>

     <tbody id="myTBody">

         <tr ordernum=1>

            <td sortvalue="0000001">1</td>

            <td sortvalue="Peter">Peter</td>

            <td sortvalue="19750119">19/01/1975</td>

          </tr>

            <tr ordernum=3>

                <td sortvalue="0000004">4</td>

                <td sortvalue="Jane">Jane</td>

                <td sortvalue="19800201">01/02/1980</td>

            </tr>

           <tr ordernum=2>

              <td sortvalue="0000002">2</td>

              <td sortvalue="Mark">Mark</td>

              <td sortvalue="19880731">31/07/1988</td>

           </tr>

            <tr ordernum=3>

                <td sortvalue="0000003">3</td>

                <td sortvalue="Jane">Jane</td>

                <td sortvalue="19600201">01/02/1960</td>

            </tr>

           <tr ordernum=4>

              <td sortvalue="0000002">2</td>

              <td sortvalue="Mark">Mark</td>

              <td sortvalue="19890731">31/07/1989</td>

           </tr>

            <tr ordernum=5>

                <td sortvalue="0000003">3</td>

                <td sortvalue="Jane">Jane</td>

                <td sortvalue="20000201">01/02/2000</td>

            </tr>

     </tbody>

</table>
 

<script type="text/javascript">

var trTagsArray = new Array();
 

function initTBody(){

  var tbodytag = document.getElementById("myTBody");

  var tbodytagChilds = tbodytag.childNodes

  var i = 0;

  for (i=0;i<tbodytagChilds.length;i++){

    if (tbodytagChilds[i].nodeName == "TR"){

      trTagsArray.push(tbodytagChilds[i]);

    }

  }

}
 
 

function reOrder(tbodyid,o1,o2,o3){

  var tbodytag = document.getElementById(tbodyid);

  var tbodytagChilds = tbodytag.childNodes;

  var splicedTrTag;

  var oValue;

  var i = 0;

  var smallestSortValue = "ZZZZZZZZZZ";

  var smallestIndex;

  var tempArray = new Array().concat(trTagsArray);

  var tempArray2 = new Array();

  var sortValue="";

  while (tbodytagChilds.length > 0){

    tbodytag.removeChild(tbodytagChilds[0]);

  }
 
 

  for (var k=3;k>=1;k--){

    oValue = eval("o" + k);

//    alert("oValue : " + oValue);

    tempArray = Quicksort(tempArray,oValue);

  }
 
 

//  tempArray = Quicksort(tempArray,3);
 

    for (i = 0; i< tempArray.length;i++){

        tbodytag.appendChild(tempArray[i]);

    }

}
 

function Quicksort(sortArray,voValue){
 

      var tempArray = new Array().concat(sortArray);

      var lessArray = new Array();

      var moreArray = new Array();

      var resultArray = new Array();

      var sortValue="";
 

      if (sortArray.length == 1){

        return sortArray[0];

      }else{
 

      pivot = tempArray.pop();

      pivotValue = getSortValue(pivot, voValue);
 

      for (i=0;i<tempArray.length;i++){

        if (voValue ==3){

          sortValue = parseInt(getSortValue(tempArray[i],voValue));

        }else{

                sortValue = getSortValue(tempArray[i],voValue);

        }

        if (sortValue <= pivotValue){

          lessArray.push(tempArray[i]);

        }else{

          moreArray.push(tempArray[i]);

        }

      }
 

      

      

      if (lessArray.length > 0){

        resultArray = resultArray.concat(Quicksort(new Array(lessArray),voValue));

      }
 

      resultArray = resultArray.concat(pivot);
 
 

      if (moreArray.length > 0){

        resultArray = resultArray.concat(Quicksort(new Array(moreArray),voValue));

      }
 

      return resultArray;

      }
 

}
 

function getSortValue(trTag,tagIndex){

  var trTagChilds = trTag.childNodes;

  var indexedTdTag;

  var numTdTag = 0;

  var j=0;

  var returnValue = "";

  for (j=0;j<trTagChilds.length;j++){

    if (trTagChilds[j].nodeName == "TD"){

      ++numTdTag;

      if (tagIndex == numTdTag){

        indexedTdTag = trTagChilds[j];

        break;

      }

    }

  }

  

  try{

    returnValue = indexedTdTag.attributes['sortvalue'].value;

  }catch(err){

    returnValue = "";

  }

  

  return returnValue;

}
 

initTBody();

</script>

Open in new window

0
 
LVL 11

Author Comment

by:mildurait
ID: 24044452
@fsze88
So if I hear you right
a) this is a burden which is way too heavy and impossible for you to carry alone?
b) only Jesus, the living Son of God, who has the authority over all Heaven and Earth would have the ability to solve the insolvable?
0
 
LVL 15

Expert Comment

by:fsze88
ID: 24046005
mildurait,
I will keep try to solve this.... give me times. Also, I interested in this question but not guarantee I can/able to solve it out....
0
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
LVL 11

Author Comment

by:mildurait
ID: 24046023
@fsze88
You've done great things for me so far, and I appreciate your help.
We might need to develop a replacement language for JavaScript, called JesusScript which would by definition support an unlimited number of concurrent recursive calls.
0
 
LVL 15

Accepted Solution

by:
fsze88 earned 500 total points
ID: 24046474
please try this,
note : this is not responsible for error and/or guarantee faster than bubble sort
have a fun....
<table>

     <tr>

          <td onclick="reOrder('myTBody',1,0,0);">ID</td>

          <td onclick="reOrder('myTBody',2,3,1);">Name</td>

          <td onclick="reOrder('myTBody',3,2,1);">DOB</td></tr>

     </tr>

     <tbody id="myTBody">

         <tr ordernum=1>

            <td sortvalue="0000001">1</td>

            <td sortvalue="Peter">Peter</td>

            <td sortvalue="19750119">19/01/1975</td>

          </tr>

            <tr ordernum=3>

                <td sortvalue="0000004">4</td>

                <td sortvalue="Jane">Jane</td>

                <td sortvalue="19760201">01/02/1976</td>

            </tr>

           <tr ordernum=2>

              <td sortvalue="0000002">2</td>

              <td sortvalue="Mark">Mark</td>

              <td sortvalue="19880731">31/07/1988</td>

           </tr>

            <tr ordernum=3>

                <td sortvalue="0000003">3</td>

                <td sortvalue="Jane">Jane</td>

                <td sortvalue="19600201">01/02/1960</td>

            </tr>

           <tr ordernum=4>

              <td sortvalue="0000006">6</td>

              <td sortvalue="Mark">Mark</td>

              <td sortvalue="19990731">31/07/1999</td>

           </tr>

            <tr ordernum=5>

                <td sortvalue="0000005">5</td>

                <td sortvalue="Jane">Jane</td>

                <td sortvalue="19610201">01/02/1961</td>

            </tr>

     </tbody>

</table>
 

<script type="text/javascript">

var trTagsArray = new Array();
 

function initTBody(){

  var tbodytag = document.getElementById("myTBody");

  var tbodytagChilds = tbodytag.childNodes

  var i = 0;

  for (i=0;i<tbodytagChilds.length;i++){

    if (tbodytagChilds[i].nodeName == "TR"){

      trTagsArray.push(tbodytagChilds[i]);

    }

  }

}
 
 

function reOrder(tbodyid,o1,o2,o3){

  var tbodytag = document.getElementById(tbodyid);

  var tbodytagChilds = tbodytag.childNodes;

  var splicedTrTag;

  var oValue;

  var i = 0;

  var smallestSortValue = "ZZZZZZZZZZ";

  var smallestIndex;

  var tempArray = new Array().concat(trTagsArray);

  var tempArray2 = new Array();

  var sortValue="";

  while (tbodytagChilds.length > 0){

    tbodytag.removeChild(tbodytagChilds[0]);

  }
 

  for (var k=3;k>=1;k--){

    oValue = eval("o" + k);

    tempArray = Quicksort(tempArray,oValue);

  }
 

////      tempArray = Quicksort(new Array().concat(tempArray),3);

////      alert("final tempArray.length : " + tempArray.length);
 

/*

  try{

      for (i=0;i<tempArray.length;i++){

        document.write("result : " + getSortValue(tempArray[i],1) + "<br/>");

      }

  }catch(err){

    document.write('abc');

  }

*/  
 
 

    for (i = 0; i< tempArray.length;i++){

        tbodytag.appendChild(tempArray[i]);

    }
 

}
 

function Quicksort(sortArray,voValue){
 

      var resultArray = new Array();
 

      var tempArray = new Array().concat(sortArray);
 

      var lessArray = new Array();

      var moreArray = new Array();

      var pivot;

      var pivotValue;

      var sortValue="";

      

//      var element = sortArray[0];

      

//      alert("element : " + element + "<br/>");

//      alert("tempArray[0].nodeName : " + tempArray[0].nodeName + "<br/>");
 

      

      if (sortArray.length == 1){

        return sortArray[0];

      }else{

      

        pivot = tempArray.pop();

        pivotValue = getSortValue(pivot, voValue);

  

        for (i=0;i<tempArray.length;i++){

          sortValue = getSortValue(tempArray[i],voValue);

////          alert("pivotValue : " + pivotValue + " sortValue : " + sortValue + "<br/>");

          if (sortValue <= pivotValue){

            lessArray.push(tempArray[i]);

          }else{

            moreArray.push(tempArray[i]);

          }

        }
 

/*

        for (i=0;i<lessArray.length;i++){

          document.write("left : " + getSortValue(lessArray[i],voValue) + "<br/>");

        }

*/        

        if (lessArray.length > 0){

          resultArray = new Array().concat( resultArray.concat(Quicksort( new Array().concat(lessArray) , voValue) ) );

        }

  

////        alert("pivotValue : " + pivotValue);

        resultArray = new Array().concat(resultArray.concat(pivot));

        

/*  

        for (i=0;i<moreArray.length;i++){

          document.write("right : " + getSortValue(moreArray[i],voValue) + "<br/>");

        }

  */

        

        if (moreArray.length > 0){

          resultArray = resultArray.concat(Quicksort(new Array().concat(moreArray) , voValue));

        }

        return resultArray;

      }
 

}
 

function getSortValue(trTag,tagIndex){

  var trTagChilds = trTag.childNodes;

  var indexedTdTag;

  var numTdTag = 0;

  var j=0;

  var returnValue = "";

  for (j=0;j<trTagChilds.length;j++){

    if (trTagChilds[j].nodeName == "TD"){

      ++numTdTag;

      if (tagIndex == numTdTag){

        indexedTdTag = trTagChilds[j];

        break;

      }

    }

  }

  

  try{

    returnValue = indexedTdTag.attributes['sortvalue'].value;

  }catch(err){

    returnValue = "";

  }

  

  return returnValue;

}
 

initTBody();

</script>

Open in new window

0
 
LVL 15

Expert Comment

by:fsze88
ID: 24059156
did you tried it? It works on QuickSort Algorithm
0
 
LVL 11

Author Closing Comment

by:mildurait
ID: 31565278
Well done again!
Thanks for your time and expertise.
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

In my daily work (mainly using ASP.net), I need to write a lot of JavaScript code. One of the most repetitive tasks I do are the jQuery Ajax calls. You know: (CODE) I don't know if for you it's the same, but for me is soooo tedious to write the …
Introduction HTML checkboxes provide the perfect way for a web developer to receive client input when the client's options might be none, one or many.  But the PHP code for processing the checkboxes can be confusing at first.  What if a checkbox is…
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…

863 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

Need Help in Real-Time?

Connect with top rated Experts

26 Experts available now in Live!

Get 1:1 Help Now