JavaScript BubbleSort

Question

Hi,

Have a bubblesort routine similar the this. I need to make it more efficient by stopping the loop when the array is sorted or if the array is already sorted.

function sortNumbers(listbox) {
  var x, y, holder;
  // The Bubble Sort method.
  for(x = 0; x < ranarray.length; x++) {
    for(y = 0; y < (ranarray.length-1); y++) {
      if(ranarray[y] > ranarray[y+1]) {
        holder = ranarray[y+1];
        ranarray[y+1] = ranarray[y];
        ranarray[y] = holder;
      }
    }
  }

Answer 1

Before enter the inner loop, create a boolean to check if a swap occured inside the inner loop. When the there is no swap the array is sorted.

function sortNumbers(listbox) { 
  var x, y, holder; 
  // The Bubble Sort method. 
  for(x = 0; x < ranarray.length; x++) { 
    var swapOccured = false;
    for(y = 0; y < (ranarray.length-1); y++) { 
      if(ranarray[y] > ranarray[y+1]) { 
        holder = ranarray[y+1]; 
        ranarray[y+1] = ranarray[y]; 
        ranarray[y] = holder; 
        swapOccured = true;
      } 
    }
    if (!swapOccured) break; 
  } 

Answer 2

Check if a swap occurs in the inner loop. When there is no swap during one run, the list is sorted.

Also, you can use the x value to determine the last item that you need to look at in the inner loop. After x runs the last x items are always in the right place.

function sortNumbers(listbox) {
  var done = false;
  for (var x = 1; !done; x++) {
    done = true;
    for (var y = 0; y < ranarray.length - x; y++) {
      if (ranarray[y] > ranarray[y + 1]) {
        var holder = ranarray[y + 1];
        ranarray[y + 1] = ranarray[y];
        ranarray[y] = holder;
        done = false;
      }
    }
  }
}