A few sorting algorithms written in JavaScript.
/*
-----------------------------------------------------------------------------
Computer science in JavaScript: Selection sort
-----------------------------------------------------------------------------
article: http://www.nczonline.net/blog/2009/09/08/computer-science-in-javascript-selection-sort/
code: https://github.com/nzakas/computer-science-in-javascript/
*/
/**
* Swaps two values in an array.
*
* @param {Array} items The array containing the items.
* @param {int} firstIndex Index of first item to swap.
* @param {int} secondIndex Index of second item to swap.
* @return {void}
*/
function selectionSortSwap(items, firstIndex, secondIndex){
var temp = items[firstIndex];
items[firstIndex] = items[secondIndex];
items[secondIndex] = temp;
}
/**
* A selection sort implementation in JavaScript. The array
* is sorted in-place.
*
* @param {Array} items An array of items to sort.
* @return {Array} The sorted array.
*/
function selectionSort(items){
var len = items.length,
min, i, j;
for (i=0; i < len; i++){
// set minimum to this position
min = i;
// check the rest of the array to see if anything is smaller
for (j=i+1; j < len; j++){
if (items[j] < items[min]){
min = j;
}
}
// if the minimum isn't in the position, swap it
if (i != min){
selectionSortSwap(items, i, min);
}
}
return items;
}
/*
-----------------------------------------------------------------------------
Computer science in JavaScript: Quicksort
-----------------------------------------------------------------------------
article: http://www.nczonline.net/blog/2012/11/27/computer-science-in-javascript-quicksort/
code: https://github.com/nzakas/computer-science-in-javascript/
*/
/**
* Swaps two values in an array.
*
* @param {Array} items The array containing the items.
* @param {int} firstIndex Index of first item to swap.
* @param {int} secondIndex Index of second item to swap.
* @return {void}
*/
function quickSortSwap(items, firstIndex, secondIndex){
var temp = items[firstIndex];
items[firstIndex] = items[secondIndex];
items[secondIndex] = temp;
}
function partition(items, left, right) {
var pivot = items[Math.floor((right + left) / 2)], // pivot value is middle item
i = left, // starts from left and goes right to pivot index
j = right; // starts from right and goes left to pivot index
// while the two indices don't match
while (i <= j) {
// if the item on the left is less than the pivot, continue right
while (items[i] < pivot) {
i++;
}
// if the item on the right is greater than the pivot, continue left
while (items[j] > pivot) {
j--;
}
// if the two indices still don't match, swap the values
if (i <= j) {
quickSortSwap(items, i, j);
// change indices to continue loop
i++;
j--;
}
}
// this value is necessary for recursion
return i;
}
/**
* A quicksort implementation in JavaScript. The array
* is sorted in place.
*
* @param {Array} items An array of items to sort.
* @return {Array} The sorted array.
*/
function quickSort(items, left, right) {
var index;
// performance - don't sort an array with zero or one items
if (items.length > 1) {
// fix left and right values - might not be provided
left = typeof left != "number" ? 0 : left;
right = typeof right != "number" ? items.length - 1 : right;
// split up the entire array
index = partition(items, left, right);
// if the returned index
if (left < index - 1) {
quickSort(items, left, index - 1);
}
if (index < right) {
quickSort(items, index, right);
}
}
return items;
}
/*
-----------------------------------------------------------------------------
Computer science in JavaScript: Insertion sort
-----------------------------------------------------------------------------
article: http://www.nczonline.net/blog/2012/09/17/computer-science-in-javascript-insertion-sort/
code: https://github.com/nzakas/computer-science-in-javascript/
*/
/**
* An insertion sort implementation in JavaScript. The array
* is sorted in-place.
*
* @param {Array} items An array of items to sort.
* @return {Array} The sorted array.
*/
function insertionSort(items) {
var len = items.length, // number of items in the array
value, // the value currently being compared
i, // index into unsorted section
j; // index into sorted section
for (i=0; i < len; i++) {
// store the current value because it may shift later
value = items[i];
/*
* Whenever the value in the sorted section is greater than the value
* in the unsorted section, shift all items in the sorted section over
* by one. This creates space in which to insert the value.
*/
for (j=i-1; j > -1 && items[j] > value; j--) {
items[j+1] = items[j];
}
items[j+1] = value;
}
return items;
}
/*
-----------------------------------------------------------------------------
Computer science in JavaScript: Merge sort
-----------------------------------------------------------------------------
article: http://www.nczonline.net/blog/2012/10/02/computer-science-and-javascript-merge-sort/
code: https://github.com/nzakas/computer-science-in-javascript/
*/
/*
* Iterative merge sort implementation in JavaScript
* Copyright (c) 2009-2011 Nicholas C. Zakas
*/
/**
* Merges to arrays in order based on their natural
* relationship.
*
* @param {Array} left The first array to merge.
* @param {Array} right The second array to merge.
* @return {Array} The merged array.
*/
function merge(left, right){
var result = [];
while (left.length > 0 && right.length > 0){
if (left[0] < right[0]){
result.push(left.shift());
} else {
result.push(right.shift());
}
}
result = result.concat(left).concat(right);
//make sure remaining arrays are empty
left.splice(0, left.length);
right.splice(0, right.length);
return result;
}
/**
* Sorts an array in ascending natural order using
* merge sort.
*
* @param {Array} items The array to sort.
* @return {Array} The sorted array.
*/
function mergeSort(items){
// Terminal condition - don't need to do anything for arrays with 0 or 1 items
if (items.length < 2) {
return items;
}
var work = [],
i,
len;
for (i=0, len=items.length; i < len; i++){
work.push([items[i]]);
}
work.push([]); //in case of odd number of items
for (var lim=len; lim > 1; lim = Math.floor((lim+1)/2)){
for (var j=0,k=0; k < lim; j++, k+=2){
work[j] = merge(work[k], work[k+1]);
}
work[j] = []; //in case of odd number of items
}
return work[0];
}
/*
* Recursive merge sort implementation in JavaScript
* Copyright (c) 2012 Nicholas C. Zakas
*/
/**
* Merges to arrays in order based on their natural
* relationship.
*
* @param {Array} left The first array to merge.
* @param {Array} right The second array to merge.
* @return {Array} The merged array.
*/
function recursiveMerge(left, right){
var result = [],
il = 0,
ir = 0;
while (il < left.length && ir < right.length){
if (left[il] < right[ir]){
result.push(left[il++]);
} else {
result.push(right[ir++]);
}
}
return result.concat(left.slice(il)).concat(right.slice(ir));
}
/**
* Sorts an array in ascending natural order using
* merge sort.
*
* @param {Array} items The array to sort.
* @return {Array} The sorted array.
*/
function recursiveMergeSort(items){
if (items.length < 2) {
return items;
}
var middle = Math.floor(items.length / 2),
left = items.slice(0, middle),
right = items.slice(middle),
params = recursiveMerge(recursiveMergeSort(left), recursiveMergeSort(right));
// Add the arguments to replace everything between 0 and last item in the array
params.unshift(0, items.length);
items.splice.apply(items, params);
return items;
}
/*
-----------------------------------------------------------------------------
Computer science in JavaScript: Bubble sort
-----------------------------------------------------------------------------
article: http://www.nczonline.net/blog/2009/05/26/computer-science-in-javascript-bubble-sort/
code: https://github.com/nzakas/computer-science-in-javascript/
*/
// bubble-sort.js
/**
* Swaps two values in an array.
*
* @param {Array} items The array containing the items.
* @param {int} firstIndex Index of first item to swap.
* @param {int} secondIndex Index of second item to swap.
* @return {void}
*/
function bubbleSortSwap(items, firstIndex, secondIndex){
var temp = items[firstIndex];
items[firstIndex] = items[secondIndex];
items[secondIndex] = temp;
}
/**
* A bubble sort implementation in JavaScript. The array
* is sorted in-place.
*
* @param {Array} items An array of items to sort.
* @return {Array} The sorted array.
*/
function bubbleSort(items){
var len = items.length,
i, j, stop;
for (i=0; i < len; i++){
for (j=0, stop=len-i; j < stop; j++){
if (items[j] > items[j+1]){
bubbleSortSwap(items, j, j+1);
}
}
}
return items;
}
// bubble-sort-2.js
//
// An alternative form of bubble sort can be accomplished by going through
// the array in the reverse order, so the items at the front of the array
// are placed in order first. To do so, simply reverse the loops.
/**
* Swaps two values in an array.
*
* @param {Array} items The array containing the items.
* @param {int} firstIndex Index of first item to swap.
* @param {int} secondIndex Index of second item to swap.
* @return {void}
*/
function bubbleSort2Swap(items, firstIndex, secondIndex){
var temp = items[firstIndex];
items[firstIndex] = items[secondIndex];
items[secondIndex] = temp;
}
/**
* A bubble sort implementation in JavaScript. The array
* is sorted in-place. This uses two reversed loops that
* count down instead of counting up.
*
* @param {Array} items An array of items to sort.
* @return {Array} The sorted array.
*/
function bubbleSort2(items){
var len = items.length,
i, j;
for (i=len-1; i >= 0; i--){
for (j=len-i; j >= 0; j--){
if (items[j] < items[j-1]){
bubbleSort2Swap(items, j, j-1);
}
}
}
return items;
}
//
// List Sorting Perfomance
//
// Jon LaBelle, <jon@jonlabelle.com>
//
// CONFIG
// How many unsorted list iterations will be performed
var unsortedListIterations = 100000;
// How many items will be generated for each unsorted list.
var unsortedListLength = 100;
// Unsorted list value range
// ex: for list values between 1-100, set to `101`/
var unsortedListRange = 101;
// get a random list of numbers
function getUnsortedList() {
var list = new Array();
for (var i = 0; i < unsortedListLength; i++) {
list.push(Math.floor(Math.random() * unsortedListRange));
}
return list;
}
// START
console.time('selectionSort timer');
for (i = 0; i < unsortedListIterations; ++i) {
selectionSort(getUnsortedList());
}
console.timeEnd('selectionSort timer');
//
console.time('quickSort timer');
for (i = 0; i < unsortedListIterations; ++i) {
quickSort(getUnsortedList());
}
console.timeEnd('quickSort timer');
//
console.time('insertionSort timer');
for (i = 0; i < unsortedListIterations; ++i) {
insertionSort(getUnsortedList())
}
console.timeEnd('insertionSort timer');
//
console.time('mergeSort timer');
for (i = 0; i < unsortedListIterations; ++i) {
mergeSort(getUnsortedList());
}
console.timeEnd('mergeSort timer');
//
console.time('recursiveMergeSort timer');
for (i = 0; i < unsortedListIterations; ++i) {
recursiveMergeSort(getUnsortedList());
}
console.timeEnd('recursiveMergeSort timer');
//
console.time('bubbleSort timer');
for (i = 0; i < unsortedListIterations; ++i) {
bubbleSort(getUnsortedList());
}
console.timeEnd('bubbleSort timer');
//
console.time('bubbleSort2 timer');
for (i = 0; i < unsortedListIterations; ++i) {
bubbleSort2(getUnsortedList());
}
console.timeEnd('bubbleSort2 timer');