sorting/insertionsort.js

  1. (function (exports) {
  2.   'use strict';
  4.   function compare(a, b) {
  5.     return a - b;
  6.   }
  8.   /**
  9.    * Insertionsort algorithm.<br><br>
  10.    * Time complexity: O(N^2).
  11.    *
  12.    * @example
  13.    *
  14.    * var sort = require('path-to-algorithms/src' +
  15.    * '/sorting/insertion-sort').insertionSort;
  16.    * console.log(sort([2, 5, 1, 0, 4])); // [ 0, 1, 2, 4, 5 ]
  17.    *
  18.    * @public
  19.    * @module sorting/insertionsort
  20.    * @param {Array} array Input array.
  21.    * @param {Function} cmp Optional. A function that defines an
  22.    * alternative sort order. The function should return a negative,
  23.    * zero, or positive value, depending on the arguments.
  24.    * @return {Array} Sorted array.
  25.    */
  26.   function insertionSort(array, cmp) {
  27.     cmp = cmp || compare;
  28.     var current;
  29.     var j;
  30.     for (var i = 1; i < array.length; i += 1) {
  31.       current = array[i];
  32.       j = i - 1;
  33.       while (j >= 0 && cmp(array[j], current) > 0) {
  34.         array[j + 1] = array[j];
  35.         j -= 1;
  36.       }
  37.       array[j + 1] = current;
  38.     }
  39.     return array;
  40.   }
  42.   exports.insertionSort = insertionSort;
  44. })(typeof window === 'undefined' ? module.exports : window);