Skip to main content

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');