I wanted to compare some of the various, famous sort algorithms, and I decided to write them using JavaScript. I implemented them by extending Array, and they are all listed below. I wouldn't recommend using any of these however, they are not optimized and the built-in sort() can beat all of them under almost all circumstances. These are presented here solely for educational purposes.

/*!
 * Exent the JavaScript Array object
 * to perform various sort algorithms
 * 
 * @author Christopher Stoll
 * @version 1.0
 */

/**
 * extend Array to do bubble sort
 *
 * @this {Array}
 */
Array.prototype.bubbleSort = function(){
  var morework = true,
    holder = 0;
    
  while(morework) {
    morework = false;
    for(var i=0; i<this.length-1; i++){
      if(this[i] > this[i+1]){
        holder = this[i];
        this[i] = this[i+1];
        this[i+1] = holder;
        morework = true;
      }
    }
  }
}

/**
 * extend Array to do cocktail sort
 *
 * @this {Array}
 */
Array.prototype.cocktailSort = function(){
  var morework = true,
    holder = 0;
    
  while(morework) {
    morework = false;
    for(var i=0; i<this.length-1; i++){
      if(this[i] > this[i+1]){
        holder = this[i];
        this[i] = this[i+1];
        this[i+1] = holder;
        morework = true;
      }
    }
    
    if(!morework){
      break;
    }
    
    for(var i=this.length-1; i>0; i--){
      if(this[i] > this[i+1]){
        holder = this[i];
        this[i] = this[i+1];
        this[i+1] = holder;
        morework = true;
      }
    }
  }
}

/**
 * extend Array to do selection sort
 *
 * @this {Array}
 */
Array.prototype.selectionSort = function(){
  var holder = 0,
    min_mark = 0,
    min_value = 0;
    
  for(var i=0; i<this.length; i++){
    min_mark = i;
    min_value = this[min_mark];
    
    for(var j=i; j<this.length; j++){
      if(this[j] < min_value){
        min_mark = j;
        min_value = this[min_mark];
      }
    }
    
    if(min_mark != i){
      holder = this[i];
      this[i] = this[min_mark];
      this[min_mark] = holder;
    }
  }
}

/**
 * extend Array to do insertion sort
 *
 * @this {Array}
 */
Array.prototype.insertionSort = function(){
  var holder = 0,
    workon = 0,
    morework = true;
    
  for(var i=1; i<this.length; i++){
    holder = this[i];
    workon = i - 1;
    morework = true;
    
    while(morework){
      if(this[workon] > holder){
        this[workon+1] = this[workon];
        workon = workon - 1;
        
        if(workon < 0){
          morework = false;
        }
      } else {
        morework = false;
      }
    }
    
    this[workon+1] = holder;
  }
}

/**
 * merge worker for merge sort worker
 *
 * @private
 * @this {Array}
 * @param {Array} pal left side to merge
 * @param {Array} par right side to merge
 * @return {Array} merged array
 */
Array.prototype.mergeSortWorkerMerge = function(pal, par){
  var result = [];
  
  while(pal.length > 0 && par.length >0){
    if(pal[0] <= par[0]){
      result.push(pal[0]);
      pal = pal.slice(1);
    } else {
      result.push(par[0]);
      par = par.slice(1);
    }
  }
  
  if(pal.length > 0){
    result = result.concat(pal);
  }else{
    result = result.concat(par);
  }
  
  return result;
}

/**
 * worker for merge sort
 *
 * @private
 * @this {Array}
 * @param {Array} parray The array to work with
 * @return {Array} sorted array
 */
Array.prototype.mergeSortWorker = function(parray){
  var result = [],
    left = [],
    right = [],
    middle = Math.floor(parray.length / 2);
    
  if(parray.length > 1){
    for(var i=0; i<middle; i++){
      left.push(parray[i]);
    }
    for(var i=middle; i<parray.length; i++){
      right.push(parray[i]);
    }
    
    left = this.mergeSortWorker(left);
    right = this.mergeSortWorker(right);
    
    if(left[left.length] > right[0]){
      result = this.mergeSortWorkerMerge(left, right);
    } else {
      result = this.mergeSortWorkerMerge(right, left);
    }
    
    return result;
  } else {
    return parray;
  }
}

/**
 * extend Array to do merge sort
 *
 * @this {Array}
 * @return {Array} sorted array
 */
Array.prototype.mergeSort = function(){
  var result = [];
  
  result = this.mergeSortWorker(this);
  return result;
}

/**
 * sift down worker for heap sort
 *
 * @private
 * @this {Array}
 * @param {Array} parray The array to work with
 * @param {numeric} pbegin Where to start sift down
 * @param {numeric} pend Where to end sift down
 * @return {Array} heapified array
 */
Array.prototype.heapSortSiftDown = 
function(parray, pbegin, pend){
  var root = pbegin,
    child = 0;
  
  while((root * 2 + 1) <= pend){
    child = root * 2 + 1;
    
    if((child < pend) && 
    (parray[child] < parray[child+1])){
      child++;
    }
    
    if(parray[root] < parray[child]){
      holder = parray[root];
      parray[root] = parray[child];
      parray[child] = holder;
      root = child;
    } else {
      break;
    }
  }
  
  return parray;
}

/**
 * heapify worker for heap sort
 *
 * @private
 * @this {Array}
 * @param {Array} parray The array to work with
 * @return {Array} heapified array
 */
Array.prototype.heapSortHeapify = function(parray){
  var workcount = Math.floor((parray.length - 2) / 2);
  
  for(var i=workcount; i>=0; i--){
    parray = 
    this.heapSortSiftDown(parray, i, parray.length-1);
  }
  
  return parray;
}

/**
 * extend Array to do heap sort
 *
 * @this {Array}
 * @return {Array} sorted array
 */
Array.prototype.heapSort = function(){
  var result = this.heapSortHeapify(this),
    holder = 0;
  
  for(var i=this.length-1; i>0; i--){
    holder = result[0];
    result[0] = result[i];
    result[i] = holder;
    
    result = result.heapSortSiftDown(result, 0, i-1);
  }
  
  return result;
}

/**
 * partition worker for quick sort
 *
 * @private
 * @this {Array}
 * @param {Array} parray The array to work with
 * @param {numeric} pbegin The starting point
 * @param {numeric} pend The ending point
 * @return {numeric} Partition index
 */
Array.prototype.quickSortWorkerPartition = 
function(parray, pbegin, pend){
  var holder = 0,
    pivotval = parray[pend],
    partindex = pbegin - 1;
  
  for(var i=pbegin; i<pend; i++){
    if(pivotval <= parray[i]){
      partindex++;
      holder = parray[i];
      parray[i] = parray[partindex];
      parray[partindex] = holder;
    }
  }
  
  parray[pend] = parray[partindex + 1];
  parray[partindex + 1] = pivotval;
  
  return partindex + 1;
}

/**
 * worker for quick sort
 *
 * @private
 * @this {Array}
 * @param {Array} parray The array to work with
 * @param {numeric} pbegin The starting point
 * @param {numeric} pend The ending point
 * @return {Array} sorted array
 */
Array.prototype.quickSortWorker = 
function(parray, pbegin, pend){
  var newpivot = 0;
  
  if(pbegin < pend){
    newpivot = 
      this.quickSortWorkerPartition(
        parray, pbegin, pend);
    parray = 
      this.quickSortWorker(
        parray, pbegin, newpivot-1);
    parray = 
      this.quickSortWorker(
        parray, newpivot+1, pend);
  }
  
  return parray;
}

/**
 * extend Array to do quick sort
 *
 * @this {Array}
 */
Array.prototype.quickSort = function(){
  return this.quickSortWorker(this, 0, this.length-1);
}

Tags: Blogger JavaScript Code Algorithms

Published: 2010-04-09