Javascript Radix Sort

Question

私はしばらくWebを見てきましたが、一般的に使用されているRadix Sortの '安定した'デファクト実装があるのでしょうか？

基数ソートの2つの分類は、最下位桁（LSD）基数ソートと最上位桁（MSD）基数ソートです。

LSDまたはMSDの例をお探しください。

Answer 1

私のバージョンは、より冗長ですが、それでも多数の項目のためにすぐに実行されます。

 var testArray = [ 331, 454, 230, 34, 343, 45, 59, 453, 345, 231, 9 ]; 

    function radixBucketSort (arr) { 
    var idx1, idx2, idx3, len1, len2, radix, radixKey; 
    var radices = {}, buckets = {}, num, curr; 
    var currLen, radixStr, currBucket; 

    len1 = arr.length; 
    len2 = 10; // radix sort uses ten buckets 

    // find the relevant radices to process for efficiency   
    for (idx1 = 0;idx1 < len1;idx1++) { 
     radices[arr[idx1].toString().length] = 0; 
    } 

    // loop for each radix. For each radix we put all the items 
    // in buckets, and then pull them out of the buckets. 
    for (radix in radices) {   
     // put each array item in a bucket based on its radix value 
     len1 = arr.length; 
     for (idx1 = 0;idx1 < len1;idx1++) { 
     curr = arr[idx1]; 
     // item length is used to find its current radix value 
     currLen = curr.toString().length; 
     // only put the item in a radix bucket if the item 
     // key is as long as the radix 
     if (currLen >= radix) { 
      // radix starts from beginning of key, so need to 
      // adjust to get redix values from start of stringified key 
      radixKey = curr.toString()[currLen - radix]; 
      // create the bucket if it does not already exist 
      if (!buckets.hasOwnProperty(radixKey)) { 
      buckets[radixKey] = []; 
      } 
      // put the array value in the bucket 
      buckets[radixKey].push(curr);   
     } else { 
      if (!buckets.hasOwnProperty('0')) { 
      buckets['0'] = []; 
      } 
      buckets['0'].push(curr);   
     } 
     } 
     // for current radix, items are in buckets, now put them 
     // back in the array based on their buckets 
     // this index moves us through the array as we insert items 
     idx1 = 0; 
     // go through all the buckets 
     for (idx2 = 0;idx2 < len2;idx2++) { 
     // only process buckets with items 
     if (buckets[idx2] != null) { 
      currBucket = buckets[idx2]; 
      // insert all bucket items into array 
      len1 = currBucket.length; 
      for (idx3 = 0;idx3 < len1;idx3++) { 
      arr[idx1++] = currBucket[idx3]; 
      } 
     } 
     } 
     buckets = {}; 
    } 
    } 
    radixBucketSort(testArray); 
    console.dir(testArray);   

Answer 2

JavascriptのLSDのソート：

var counter = [[]]; 
function sortLSD(array, maxDigitSymbols) { 
    var mod = 10; 
    var dev = 1; 
    for (var i = 0; i < maxDigitSymbols; i++, dev *= 10, mod *= 10) { 
     for (var j = 0; j < array.length; j++) { 
      var bucket = parseInt((array[j] % mod)/dev); 
      if (counter[bucket] == null) { 
       counter[bucket] = []; 
      } 
      counter[bucket].push(array[j]); 
     } 
     var pos = 0; 
     for (var j = 0; j < counter.length; j++) { 
      var value = null ; 
      if (counter[j] != null) { 
       while ((value = counter[j].shift()) != null) { 
        array[pos++] = value; 
       } 
      } 
     } 
    } 
    return array; 
} 
var test = [22, 1,2,9,3,2,5,14,66]; 
console.log(sortLSD(test, 2)); 

Answer 3

以下のコードを使用すると、多数の項目に配列を渡すことができます。

var counter = [[]]; // Radix sort Array container to hold arrays from 0th digit to 9th digits 
 
    function radixSortLSD(array) { 
 
     var max = 0, mod = 10,dev = 1; //max 
 
     for(var i=0;i<array.length;i++){ 
 
      if(array[i] >max){ 
 
       max = array[i]; 
 
      } 
 
     } 
 
     // determine the large item length 
 
     var maxDigitLength = (max+'').length; 
 
     for (var i = 0; i < maxDigitLength; i++, dev *= 10, mod *= 10) { 
 
      for(var j = 0; j < array.length; j++) { 
 
       var bucket = Math.floor((array[j] % mod)/dev);// Formula to get the significant digit 
 
       if(counter[bucket]==undefined) { 
 
        counter[bucket] = []; 
 
       } 
 
       counter[bucket].push(array[j]); 
 
      } 
 
      var pos = 0; 
 
      for(var j = 0; j < counter.length; j++) { 
 
       var value = undefined; 
 
       if(counter[j]!=undefined) { 
 
        while ((value = counter[j].shift()) != undefined) { 
 
         array[pos++] = value; 
 
        } 
 
       } 
 
      } 
 
     } 
 
     console.log("ARRAY: "+array); 
 
    }; 
 
var sampleArray = [1,121,99553435535353534,345,0]; 
 
radixSortLSD(sampleArray);

Answer 4

基数ソートは素晴らしい線形時間ソートアルゴリズムです。 CPUとGPUのための多くの高速実装が行われています。ここで私のC++の実装をJavaScriptに変換したものがあります。それは私がこの本は、基数ソートの不可解な起源を提供CRLの第3版のセクション8.3

で基数ソートが発生した符号なし整数High Performance Radix Sort LSD

Answer 5

の配列をソートするために5 50倍に高速化JavaScriptの組み込みのソートと比較しています。 MSDのバージョンは古くて扱いにくいものだと説明しています。また、LSDの実施を勧告した。

ここでは、この手法を使用して基数ソートの実装を提供します。擬似コードで

レッツ・スタート：

/** 
* @param k: the max of input, used to create a range for our buckets 
* @param exp: 1, 10, 100, 1000, ... used to calculate the nth digit 
*/ 
Array.prototype.countingSort = function (k, exp) { 
    /* eslint consistent-this:0 */ 
    /* self of course refers to this array */ 
    const self = this; 

    /** 
    * let's say the this[i] = 123, if exp is 100 returns 1, if exp 10 returns 2, if exp is 1 returns 3 
    * @param i 
    * @returns {*} 
    */ 
    function index(i) { 
     if (exp) 
      return Math.floor(self[i]/exp) % 10; 
     return i; 
    } 

    const LENGTH = this.length; 

    /* create an array of zeroes */ 
    let C = Array.apply(null, new Array(k)).map(() => 0); 
    let B = []; 

    for (let i = 0; i < LENGTH; i++) 
     C[index(i)]++; 

    for (let i = 1; i < k; i++) 
     C[i] += C[i - 1]; 

    for (let i = LENGTH - 1; i >= 0; i--) { 
     B[--C[index(i)]] = this[i]; 
    } 

    B.forEach((e, i) => { 
     self[i] = e 
    }); 
} 

そして、それが唯一のトリッキーな部分だが、残りはここ

Array.prototype.radixSort = function() { 
    const MAX = Math.max.apply(null, this); 

    /* let's say the max is 1926, we should only use exponents 1, 10, 100, 1000 */ 
    for (let exp = 1; MAX/exp > 1; exp *= 10) { 
     this.countingSort(10, exp); 
    } 
} 

今非常に簡単ですどのようにあなたができることですこのメソッドをテストする

let a = [589, 111, 777, 65, 124, 852, 345, 888, 553, 654, 549, 448, 222, 165]; 
a.radixSort() 
console.log(a); 

最後に、この特定のアルゴリズムは、counting-sortがインプレースソートアルゴリズムであるためにのみ機能します。これは、2つの要素が結びついている場合、入力配列内の順序が保持されることを意味します。

Answer 6

次の関数は、Uint32値のLSB基数ソートを行いません。ところで、組み込みソート関数よりも高速です。

それは限り、彼らは唯一の32ビット値を含んでいて、パフォーマンスを向上させるために型指定された配列を使用していますが、プレーンな配列を渡す場合と同じように正常に動作します：

function radixSortUint32(input) { 
    const arrayConstr = input.length < (1 << 16) ? 
    Uint16Array : 
    Uint32Array; 
    const numberOfBins = 256 * 4; 
    let count = new arrayConstr(numberOfBins); 

    let output = new Uint32Array(input.length); 

    // count all bytes in one pass 
    for (let i = 0; i < input.length; i++) { 
    let val = input[i]; 
    count[val & 0xFF]++; 
    count[((val >> 8) & 0xFF) + 256]++; 
    count[((val >> 16) & 0xFF) + 512]++; 
    count[((val >> 24) & 0xFF) + 768]++; 
    } 

    // create summed array 
    for (let j = 0; j < 4; j++) { 
    let t = 0, 
     sum = 0, 
     offset = j * 256; 
    for (let i = 0; i < 256; i++) { 
     t = count[i + offset]; 
     count[i + offset] = sum; 
     sum += t; 
    } 
    } 

    for (let i = 0; i < input.length; i++) { 
    let val = input[i]; 
    output[count[val & 0xFF]++] = val; 
    } 
    for (let i = 0; i < input.length; i++) { 
    let val = output[i]; 
    input[count[((val >> 8) & 0xFF) + 256]++] = val; 
    } 
    for (let i = 0; i < input.length; i++) { 
    let val = input[i]; 
    output[count[((val >> 16) & 0xFF) + 512]++] = val; 
    } 
    for (let i = 0; i < input.length; i++) { 
    let val = output[i]; 
    input[count[((val >> 24) & 0xFF) + 768]++] = val; 
    } 

    return input; 
} 

は、ここでは、Int32のために上記を再利用方法を説明します値：

function radixSortInt32(input) { 
    // make use of ArrayBuffer to "reinterpret cast" 
    // the Int32Array as a Uint32Array 
    let uinput = input.buffer ? 
    new Uint32Array(input.buffer): 
    Uint32Array.from(input); 

    // adjust to positive nrs 
    for (let i = 0; i < uinput.length; i++) { 
    uinput[i] += 0x80000000; 
    } 

    // re-use radixSortUint32 
    radixSortUint32(uinput); 

    // adjust back to signed nrs 
    for (let i = 0; i < uinput.length; i++) { 
    uinput[i] -= 0x80000000; 
    } 

    // for plain arrays, fake in-place behaviour 
    if (input.buffer === undefined){ 
    for (let i = 0; i < input.length; i++){ 
     input[i] = uinput[i]; 
    } 
    } 

    return input; 
} 

そしてFloat32値についても同様のトリック：

function radixSortFloat32(input) { 
    // make use of ArrayBuffer to "reinterpret cast" 
    // the Float32Array as a Uint32Array 
    let uinput = input.buffer ? 
    new Uint32Array(input.buffer) : 
    new Uint32Array(Float32Array.from(input).buffer); 

    // Similar to radixSortInt32, but uses a more complicated trick 
    // See: http://stereopsis.com/radixSort.html 
    for (let i = 0; i < uinput.length; i++) { 
    if (uinput[i] & 0x80000000) { 
     uinput[i] ^= 0xFFFFFFFF; 
    } else { 
     uinput[i] ^= 0x80000000; 
    } 
    } 

    // re-use radixSortUint32 
    radixSortUint32(uinput); 

    // adjust back to original floating point nrs 
    for (let i = 0; i < uinput.length; i++) { 
    if (uinput[i] & 0x80000000) { 
     uinput[i] ^= 0x80000000; 
    } else { 
     uinput[i] ^= 0xFFFFFFFF; 
    } 
    } 

    if (input.buffer === undefined){ 
    let floatTemp = new Float32Array(uinput.buffer); 
    for(let i = 0; i < input.length; i++){ 
     input[i] = floatTemp[i]; 
    } 
    } 

    return input; 
} 

32ビット以下のすべてのTypedArraysで動作するこれらの関数を作成しました。つまり：

• Uint32Array
• Int32Array
• Float32Array
• Uint16Array
• Int16Array
• Uint8Array
• Int8Array
• あなたはすべての値がこれらの基準のいずれかをフィット知っている任意のプレーンアレー

Full gist here。後でFloat64に行ってもいいかもしれないし、すべてのjavascript番号を基本的にサポートしています。

TypedArray benchmarks shows radix beats the built-in sort function。

It's faster with plain arrays too, although not quite as much because of the added overhead