JavaScript Sort Algorithms
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);
}
