Home Articles FAQs XREF Games Software Instant Books BBS About FOLDOC RFCs Feedback Sitemap
irt.Org
#

Q501 Is there any quick non-recursive sort?

You are here: irt.org | FAQ | JavaScript | Text | Q501 [ previous next ]

The following functions were kindly provided by Matti Helin:

// Uses Iterative (non-recursive) Quick Sort Algorithm
// from Knuth, D.  The art of computer programming, vol. 3
//                 sorting and searching
//
// usage: SelectTextSort(document.formname.selectname, {true|false} )
//        true  = keep selected
//        false = unselect all

function SelectTextSort( obj, opt ) { // sort by text
  var Left  = 0, Right = obj.options.length-1, top = 1;
  var lStack = new Array(), rStack = new Array();
      lStack[top] = Left; rStack[top] = Right;
  while (top!=0) {
    Left  =  lStack[top]; Right =  rStack[top]; top--;
    while (Left < Right) {
      var i = Left, j = Right, n = Left+Right;
      var k = Math.floor(n / 2)
      var x = obj.options[k].text;
      while (i <= j) {
        while (obj.options[i].text < x) { i++ }
        while (obj.options[j].text > x) { j-- }
        if (i <= j) {
          var i1= (obj.options[i].selected == true ) ? true : false
          var j1= (obj.options[j].selected == true ) ? true : false
          var q1 = obj.options[j].text;
          var q2 = obj.options[j].value;
          obj.options[j].text  = obj.options[i].text;
          obj.options[j].value = obj.options[i].value;
          obj.options[i].text  = q1;
          obj.options[i].value = q2;
          obj.options[i].selected = (j1&opt) ? true : false
          obj.options[j].selected = (i1&opt) ? true : false
          i++; j--
        }
      }
      if ((j - Left) < (Right - i)) {
        if (i < Right) { top++; lStack[top] = i; rStack[top] = Right }
        Right = j;
      }
      else {
        if (Left < j) { top++; lStack[top] = Left; rStack[top] = j }
        Left = i;
      }
    }
  }
  return true
}

// usage: SelectValueSort(document.formname.selectname, {true|false} )
//        true  = keep selected
//        false = unselect all

function SelectValueSort( obj, opt ) { // sort by value
  var Left  = 0, Right = obj.options.length-1, top = 1;
  var lStack = new Array(), rStack = new Array();
      lStack[top] = Left; rStack[top] = Right;
  while (top!=0) {
    Left  =  lStack[top]; Right =  rStack[top]; top--;
    while (Left < Right) {
      var i = Left, j = Right, n = Left+Right;
      var k = Math.floor(n / 2)
      var x = obj.options[k].value;
      while (i <= j) {
        while (obj.options[i].value < x) { i++ }
        while (obj.options[j].value > x) { j-- }
        if (i <= j) {
          var i1= (obj.options[i].selected == true ) ? true : false
          var j1= (obj.options[j].selected == true ) ? true : false
          var q1 = obj.options[j].text;
          var q2 = obj.options[j].value;
          obj.options[j].text  = obj.options[i].text;
          obj.options[j].value = obj.options[i].value;
          obj.options[i].text  = q1;
          obj.options[i].value = q2;
          obj.options[i].selected = (j1&opt) ? true : false
          obj.options[j].selected = (i1&opt) ? true : false
          i++; j--
        }
      }
      if ((j - Left) < (Right - i)) {
        if (i < Right) { top++; lStack[top] = i; rStack[top] = Right }
        Right = j;
      }
      else {
        if (Left < j) { top++; lStack[top] = Left; rStack[top] = j }
        Left = i;
      }
    }
  }
  return true
}

The same with Bubble Sort

// usage: SelectTextSort(document.formname.selectname, {true|false} )
//        true  = keep selected
//        false = unselect all
function SelectTextSort(obj, opt ) { // sort by text
 var N=obj.options.length;
 for (var i=0;i<N-1;i++) {
   for (var j=i+1;j<N;j++) {
     if ( obj.options[i].text > obj.options[j].text ) {
       var i1= (obj.options[i].selected == true ) ? true : false
       var j1= (obj.options[j].selected == true ) ? true : false
       var q1 = obj.options[j].text;
       var q2 = obj.options[j].value;
       obj.options[j].text  = obj.options[i].text;
       obj.options[j].value = obj.options[i].value;
       obj.options[i].text  = q1;
       obj.options[i].value = q2;
       obj.options[i].selected = (j1&opt) ? true : false
       obj.options[j].selected = (i1&opt) ? true : false
     }
   }
 }
 return true
}

// usage: SelectValueSort(document.formname.selectname, {true|false} )
//        true  = keep selected
//        false = unselect all
function SelectValueSort(obj, opt ) { // sort by value
 var N=obj.options.length;
 for (var i=0;i<N-1;i++) {
   for (var j=i+1;j<N;j++) {
     if ( obj.options[i].value > obj.options[j].value ) {
       var i1= (obj.options[i].selected == true ) ? true : false
       var j1= (obj.options[j].selected == true ) ? true : false
       var q1 = obj.options[j].text;
       var q2 = obj.options[j].value;
       obj.options[j].text  = obj.options[i].text;
       obj.options[j].value = obj.options[i].value;
       obj.options[i].text  = q1;
       obj.options[i].value = q2;
       obj.options[i].selected = (j1&opt) ? true : false
       obj.options[j].selected = (i1&opt) ? true : false
     }
   }
 }
 return true
}

It works beautifully in Netscape Navigator 4, Netscape Navigator 3 and Internet Explorer 4. It does not work in Netscape Navigator 2 and Internet Explorer 3 but nothing will as JavaScript 1.0 only allows read only access to the the text property.

Feedback on 'Q501 Is there any quick non-recursive sort?'

©2018 Martin Webb