javascript-algorithms/src/sorting/lsd.js at master · webcoding/javascript-algorithms

51 lines (48 loc) · 1.4 KB

(function (exports) {
  'use strict';

  /**
   * Sorts strings lexicographically.<br><br>
   * Time complexity: O(N*M) for N keys which have M or fewer digits.
   *
   * @example
   *
   * var sort = require('../src/sorting/lsd').lsd;
   * // [ 'aab', 'aaa', 'acc', 'bbb', 'bcc' ]
   * console.log(sort(['aab', 'bbb', 'aaa', 'acc', 'bcc']));
   *
   * @public
   * @module sorting/lsd
   * @param {Array} arr Array which should be sorted.
   * @param {Number} letterIdx Optional. Index to start sorting from.
   * @return {Array} Sorted array.
   */
  function lsd(arr, letterIdx) {
    var temp;
    var count;
    letterIdx = letterIdx || 1;
    for (var i = letterIdx - 1; i >= 0; i -= 1) {
      count = [];
      temp = [];
      for (var j = 0; j < arr.length; j += 1) {
        var charCode = arr[j].charCodeAt(i);
        var old = count[charCode + 1] || 0;
        count[charCode + 1] = old + 1;
      }
      for (var c = 0; c < count.length - 1; c += 1) {
        count[c] = count[c] || 0;
        count[c + 1] = count[c + 1] || 0;
        count[c + 1] += count[c];
      }
      for (j = 0; j < arr.length; j += 1) {
        var code = arr[j].charCodeAt(i);
        temp[count[code]] = arr[j];
        count[code] += 1;
      }
      for (j = 0; j < arr.length; j += 1) {
        arr[j] = temp[j];
      }
    }
    return arr;
  }

  exports.lsd = lsd;

})(typeof window === 'undefined' ? module.exports : window);

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Expand file tree

Search code, repositories, users, issues, pull requests...

Uh oh!

FilesExpand file tree

lsd.js

Latest commit

History

lsd.js

File metadata and controls

Expand file tree