Skip to content

Instantly share code, notes, and snippets.

@killwing

killwing/algorithm.js

Created June 30, 2011 02:52
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save killwing/1055529 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save killwing/1055529 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. killwing revised this gist Mar 30, 2014. 1 changed file with 50 additions and 0 deletions.
    50 changes: 50 additions & 0 deletions algorithm.js
    View file
    Original file line number Diff line number Diff line change
    @@ -12,6 +12,11 @@ Array.prototype.swap = function(a, b) {
    this[b] = tmp;
    };

    Array.prototype.reverse = function(l, r) {
    while (l < r) {
    this.swap(l++, r--);
    }
    };

    var produceRamdomArray = function(n, d) {
    d = d || 18;
    @@ -384,6 +389,45 @@ var mergeSort = function(a) {
    sort(0, a.length-1);
    };

    var mergeSortInplace = function(a) {
    var merge = function(l, m, r) {
    l = (l == undefined) ? 0 : l;
    r = (r == undefined) ? a.length-1 : r;

    var x = l;
    var y = m + 1;
    while (m < r) {
    while (x <= m && a[x] <= a[m+1]) {
    ++x;
    }

    while (y <= r && a[y] < a[x]) {
    ++y;
    }

    if (y-(m+1) > 0) {
    a.reverse(x, m);
    a.reverse(m+1, y-1);
    a.reverse(x, y-1);
    m = y - 1;
    } else {
    break;
    }
    }
    }

    var sort = function(l, r) {
    if (l < r) {
    var m = Math.floor((l+r)/2);
    sort(l, m);
    sort(m+1, r);
    merge(l, m, r);
    }
    }

    sort(0, a.length-1);
    };


    var quickSortFirst = function(a) {
    var qs = function(l, r) {
    @@ -657,6 +701,12 @@ var radixStrSort = function(a) {
    console.timeEnd('=== merge sort ===');
    checkSort(a);

    a = produceRamdomArray(10000, 6);
    console.time('=== merge sort inplace ===');
    mergeSortInplace(a);
    console.timeEnd('=== merge sort inplace ===');
    checkSort(a);

    a = produceRamdomArray(10000, 6);
    console.time('=== quick sort first ===');
    quickSortFirst(a);
  2. killwing revised this gist Mar 16, 2012. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion algorithm.js
    View file
    Original file line number Diff line number Diff line change
    @@ -40,7 +40,7 @@ var produceRamdomStrArray = function(n, d) {
    };


    var checkSort = function (a) {
    var checkSort = function(a) {
    for (var i = 0; i != a.length-1; ++i) {
    assert.ok(a[i] <= a[i+1], 'sort fail!');
    }
  3. killwing revised this gist Mar 15, 2012. 1 changed file with 41 additions and 39 deletions.
    80 changes: 41 additions & 39 deletions algorithm.js
    View file
    Original file line number Diff line number Diff line change
    @@ -566,7 +566,6 @@ var radixStrSort = function(a) {
    (function() {
    var ret, a;

    /*
    console.log('=== find same elements ===');
    ret = findSameElements([1,2,3,4,5,7,9,10], [3,4,7,10,12,13]);
    console.log('Result:', ret);
    @@ -622,74 +621,77 @@ var radixStrSort = function(a) {
    console.log('Result:', ret);

    // Sorting Ref: http://en.wikipedia.org/wiki/Sorting_algorithm
    console.log('=== bubble sort ===');
    a = produceRamdomArray(100, 2);
    a = produceRamdomArray(10000, 6);
    console.time('=== internal sort ===');
    a.sort(function(a, b) { return a - b;}); // internal sort as number
    console.timeEnd('=== internal sort ===');
    checkSort(a);

    a = produceRamdomArray(10000, 6);
    console.time('=== bubble sort ===');
    bubbleSort(a);
    console.log('Result:', a);
    console.timeEnd('=== bubble sort ===');
    checkSort(a);

    console.log('=== selection sort ===');
    a = produceRamdomArray(100, 2);
    a = produceRamdomArray(10000, 6);
    console.time('=== selection sort ===');
    selectionSort(a);
    console.log('Result:', a);
    console.timeEnd('=== selection sort ===');
    checkSort(a);

    console.log('=== insertion sort ===');
    a = produceRamdomArray(100, 2);
    a = produceRamdomArray(10000, 6);
    console.time('=== insertion sort ===');
    insertionSort(a);
    console.log('Result:', a);
    console.timeEnd('=== insertion sort ===');
    checkSort(a);

    console.log('=== shell sort ===');
    a = produceRamdomArray(100, 2);
    a = produceRamdomArray(10000, 6);
    console.time('=== shell sort ===');
    shellSort(a);
    console.log('Result:', a);
    console.timeEnd('=== shell sort ===');
    checkSort(a);

    console.log('=== merge sort ===');
    a = produceRamdomArray(100, 2);
    a = produceRamdomArray(10000, 6);
    console.time('=== merge sort ===');
    mergeSort(a);
    console.log('Result:', a);
    console.timeEnd('=== merge sort ===');
    checkSort(a);

    console.log('=== quick sort first ===');
    a = produceRamdomArray(100, 2);
    a = produceRamdomArray(10000, 6);
    console.time('=== quick sort first ===');
    quickSortFirst(a);
    console.log('Result:', a);
    console.timeEnd('=== quick sort first ===');
    checkSort(a);

    console.log('=== quick sort last ===');
    a = produceRamdomArray(100, 2);
    a = produceRamdomArray(10000, 6);
    console.time('=== quick sort last ===');
    quickSortLast(a);
    console.log('Result:', a);
    console.timeEnd('=== quick sort last ===');
    checkSort(a);

    console.log('=== heap sort ===');
    a = produceRamdomArray(100, 2);
    a = produceRamdomArray(10000, 6);
    console.time('=== heap sort ===');
    heapSort(a);
    console.log('Result:', a);
    console.timeEnd('=== heap sort ===');
    checkSort(a);

    console.log('=== radix sort ===');
    a = produceRamdomArray(1000, 6);
    a = produceRamdomArray(10000, 6);
    console.time('=== radix sort ===');
    a = radixSort(a);
    console.log('Result:', a);
    console.timeEnd('=== radix sort ===');
    checkSort(a);

    console.log('=== radix string sort ===');
    a = produceRamdomStrArray(1000, 6);
    //a = ['cbda','cbad','cbbb','cb','cbb','cba','abc','bac']; // special case
    a = radixStrSort(a);
    console.log('Result:', a);
    a = produceRamdomStrArray(10000, 6);
    console.time('=== internal string sort ===');
    a.sort(); // internal sort as string
    console.timeEnd('=== internal string sort ===');
    checkSort(a);
    */

    console.time('time test');
    a = produceRamdomStrArray(100000, 9);
    a = produceRamdomStrArray(10000, 6);
    //a = ['cbda','cbad','cbbb','cb','cbb','cba','abc','bac']; // special case
    console.time('=== radix string sort ===');
    a = radixStrSort(a);
    //a.sort(function(a, b) { return a - b;}); // internal sort for number
    //a.sort();
    console.timeEnd('time test');
    console.timeEnd('=== radix string sort ===');
    checkSort(a);
    })();

  4. killwing revised this gist Mar 15, 2012. 1 changed file with 44 additions and 29 deletions.
    73 changes: 44 additions & 29 deletions algorithm.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,4 +1,5 @@
    #!/usr/local/bin/node
    var assert = require('assert');

    // utils

    @@ -40,8 +41,8 @@ var produceRamdomStrArray = function(n, d) {


    var checkSort = function (a) {
    for (int i = 0; i != a.length-1; ++i) {
    assert(a[i] <= a[i+1]);
    for (var i = 0; i != a.length-1; ++i) {
    assert.ok(a[i] <= a[i+1], 'sort fail!');
    }
    };

    @@ -70,7 +71,7 @@ var findSameElements = function(a, b) {


    var fibonacci = function(n) {
    return (n == 0 || n == 1) ? n : fib(n-1) + fib(n-2);
    return (n == 0 || n == 1) ? n : fibonacci(n-1) + fibonacci(n-2);
    };


    @@ -230,7 +231,7 @@ var findMiddle = function(a, b, c) {
    ret = b;
    }
    return ret;
    });
    };


    var dec2bin = function(n) {
    @@ -452,7 +453,7 @@ var heapSort = function(a) {
    var j = l;
    while (true) {
    var p = 2*j+1; // left child
    if (p >= r) {
    if (p > r) {
    break;
    }

    @@ -522,38 +523,41 @@ var radixSort = function(a) {
    };


    // TODO: need fix!
    var radixStrSort = function(a) {
    // use MSD, recursive forward
    var d = 0;
    var rss = function(a, d) {
    var rss = function(arr, dd) {
    var b = [];
    for (var i = 0; i != a.length; ++i) {
    for (var i = 0; i != arr.length; ++i) {
    // get d-th char
    var j = 0;
    if (d < a[i].length) {
    j = a[i][d].charCodeAt();
    if (dd < arr[i].length) {
    j = arr[i][dd].charCodeAt();
    }

    if (b[j] == undefined) {
    b[j] = [];
    }
    b[j].push(a[i]);
    b[j].push(arr[i]);
    }

    a = [];
    for (var k = 0; k != b.length; ++k) {
    // redo if more than 1
    if (b[k].length > 1) {
    rss(b[k], d+1);
    }
    //console.log(dd, b);

    arr = [];
    for (var k = 0; k != b.length; ++k) {
    // collect
    if (b[k] != undefined) {
    a = a.concat(b[k]);
    // recursive sort if more than 1
    if (b[k].length > 1) {
    b[k] = rss(b[k], dd+1);
    }

    arr = arr.concat(b[k]);
    }
    }
    return arr;
    }
    a = rss(a, d);
    return a;
    };

    @@ -562,6 +566,7 @@ var radixStrSort = function(a) {
    (function() {
    var ret, a;

    /*
    console.log('=== find same elements ===');
    ret = findSameElements([1,2,3,4,5,7,9,10], [3,4,7,10,12,13]);
    console.log('Result:', ret);
    @@ -620,62 +625,72 @@ var radixStrSort = function(a) {
    console.log('=== bubble sort ===');
    a = produceRamdomArray(100, 2);
    bubbleSort(a);
    checkSort(a);
    console.log('Result:', a);
    checkSort(a);
    console.log('=== selection sort ===');
    a = produceRamdomArray(100, 2);
    selectionSort(a);
    checkSort(a);
    console.log('Result:', a);
    checkSort(a);
    console.log('=== insertion sort ===');
    a = produceRamdomArray(100, 2);
    insertionSort(a);
    checkSort(a);
    console.log('Result:', a);
    checkSort(a);
    console.log('=== shell sort ===');
    a = produceRamdomArray(100, 2);
    shellSort(a);
    checkSort(a);
    console.log('Result:', a);
    checkSort(a);
    console.log('=== merge sort ===');
    a = produceRamdomArray(100, 2);
    mergeSort(a);
    checkSort(a);
    console.log('Result:', a);
    checkSort(a);
    console.log('=== quick sort first ===');
    a = produceRamdomArray(100, 2);
    quickSortFirst(a);
    checkSort(a);
    console.log('Result:', a);
    checkSort(a);
    console.log('=== quick sort last ===');
    a = produceRamdomArray(100, 2);
    quickSortLast(a);
    checkSort(a);
    console.log('Result:', a);
    checkSort(a);
    console.log('=== heap sort ===');
    a = produceRamdomArray(100, 2);
    heapSort(a);
    checkSort(a);
    console.log('Result:', a);
    checkSort(a);
    console.log('=== radix sort ===');
    a = produceRamdomArray(1000, 6);
    a = radixSort(a);
    checkSort(a);
    console.log('Result:', a);
    checkSort(a);
    console.log('=== radix string sort ===');
    a = produceRamdomStrArray(6, 3);
    a = produceRamdomStrArray(1000, 6);
    //a = ['cbda','cbad','cbbb','cb','cbb','cba','abc','bac']; // special case
    a = radixStrSort(a);
    checkSort(a);
    console.log('Result:', a);
    checkSort(a);
    */

    console.time('time test');
    a = produceRamdomStrArray(100000, 9);
    a = radixStrSort(a);
    //a.sort(function(a, b) { return a - b;}); // internal sort for number
    //a.sort();
    console.timeEnd('time test');
    checkSort(a);
    })();


  5. killwing revised this gist Mar 14, 2012. 1 changed file with 275 additions and 129 deletions.
    404 changes: 275 additions & 129 deletions algorithm.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,5 +1,7 @@
    #!/usr/local/bin/node

    // utils

    Array.prototype.swap = function(a, b) {
    if (a == b) {
    return;
    @@ -9,8 +11,44 @@ Array.prototype.swap = function(a, b) {
    this[b] = tmp;
    };

    (function(a, b) {
    console.log('=== find same elements ===');

    var produceRamdomArray = function(n, d) {
    d = d || 18;
    d = Math.pow(10, d);
    var a = [];
    while (n--) {
    var b = Math.random();
    a.push(Math.round(b*d));
    }
    return a;
    };


    var produceRamdomStrArray = function(n, d) {
    var set = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    var a = [];
    while (n--) {
    var dd = d;
    var s = '';
    while (dd--) {
    s += set.charAt(Math.floor(Math.random() * set.length));
    }
    a.push(s);
    }
    return a;
    };


    var checkSort = function (a) {
    for (int i = 0; i != a.length-1; ++i) {
    assert(a[i] <= a[i+1]);
    }
    };


    // algorithms

    var findSameElements = function(a, b) {
    var ret = [];
    var i = 0;
    var j = 0;
    @@ -19,32 +57,24 @@ Array.prototype.swap = function(a, b) {
    if (a[i] < b[j]) {
    ++i;
    } else if (a[i] > b[j]) {
    ++j;
    ++j;
    } else { // a[i] == b[j]
    ret.push(a[i]);
    ++i;
    ++j;
    }
    }

    console.log('Result:', ret);
    })([1,2,3,4,5,7,9,10], [3,4,7,10,12,13]);

    return ret;
    };

    (function(n) {
    console.log('=== fibonacci recursive ===');
    var fib = function(n) {
    return (n == 0 || n == 1) ? n : fib(n-1) + fib(n-2);
    };

    for (var i = 0; i <= n; ++i) {
    console.log(fib(i));
    }
    })(10);
    var fibonacci = function(n) {
    return (n == 0 || n == 1) ? n : fib(n-1) + fib(n-2);
    };


    (function(a) {
    console.log('=== find 2nd max ===');
    var find2ndMax = function(a) {
    var max = a[0];
    var secMax = Number.NEGATIVE_INFINITY;

    @@ -56,13 +86,11 @@ Array.prototype.swap = function(a, b) {
    secMax = a[i];
    }
    }

    console.log('Result:', secMax);
    })([7,-6,7,7,7]);
    return secMax;
    };


    (function(a) {
    console.log('=== max subsequence sum ===');
    var maxSubseqSum = function(a) {
    var thisSum = 0;
    var maxSum = 0;
    for (var i = 0; i != a.length; ++i) {
    @@ -74,12 +102,11 @@ Array.prototype.swap = function(a, b) {
    }
    }

    console.log('Result:', maxSum);
    })([-2,11,-4,13,-5,-2,8]);
    return maxSum;
    };

    (function(a) {
    console.log('=== all arranges ===');

    var allRanges = function(a) {
    var exchange = function(l, r) {
    if (l == r) {
    console.log(a);
    @@ -94,28 +121,22 @@ Array.prototype.swap = function(a, b) {
    };

    exchange(0, a.length-1);
    };

    })([1,2,3,4]);

    (function(a, b) {
    console.log('=== Greatest Common Divisor & Least Common Multiple ===');

    var gcdAndLcm = function(a, b) {
    var c = a * b;

    while (b) {
    var temp = b;
    b = a % b;
    a = temp;
    }

    console.log('GCD:', a);
    console.log('LCM:', c/a);
    };

    })(6,9);

    (function(n) {
    console.log('=== matrix radio ===');

    var matrixRadio = function(n) {
    for (var i = 0; i < 2*n-1; ++i) {
    for (var j = 0; j < 2*n-1; ++j) {
    var x = Math.abs(n-1-i);
    @@ -124,45 +145,40 @@ Array.prototype.swap = function(a, b) {
    }
    process.stdout.write('\n');
    }
    })(9);
    };

    (function(n) {
    console.log('=== matrix round ===');

    var matrixRound = function(n) {
    // init arrays
    a = [];
    for (var i = 0; i != n; ++i) {
    a[i] = [];
    }

    var round = 0;
    var m=1;

    var round = 0;
    var m=1;

    while(m <= n*n) {
    while(m <= n*n) {
    for (var i=round; i<=n-round-1; ++i) {
    a[round][i] = m++;
    a[round][i] = m++;
    }
    for (var i=round+1; i<=n-round-1; ++i) {
    a[i][n-round-1] = m++;
    a[i][n-round-1] = m++;
    }
    for (var i=n-round-2; i>=round; --i) {
    a[n-round-1][i] = m++;
    a[n-round-1][i] = m++;
    }
    for (var i=n-round-2; i>=round+1; --i) {
    a[i][round] = m++;
    a[i][round] = m++;
    }
    round++;
    }

    for (var i = 0; i != n; ++i) {
    console.log(a[i]);
    round++;
    }

    })(9);
    return a;
    };

    (function(n) {
    console.log('=== is primer ===');

    var isPrimer = function(n) {
    var ret = false;
    if (n%2 != 0) {
    ret = true;
    @@ -174,13 +190,10 @@ Array.prototype.swap = function(a, b) {
    }
    }
    }
    };

    console.log('Result:', ret);

    })(437);

    (function(n) {
    console.log('=== star & dot ===');
    var starDot = function(n) {
    for (var i = 0; i != n; ++i) {
    for (var j = 0; j != i; ++j) {
    process.stdout.write('*');
    @@ -190,10 +203,10 @@ Array.prototype.swap = function(a, b) {
    }
    process.stdout.write('\n');
    }
    })(9);
    };

    (function(interval) {
    console.log('=== josephus ===');

    var josephus = function(interval) {
    var a = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1];
    var index = -1;
    for (var i = 0; i != a.length; ++i) {
    @@ -206,38 +219,35 @@ Array.prototype.swap = function(a, b) {
    a[index] = 0; // kick out
    console.log(a);
    }
    };

    })(3);

    (function(a, b, c) {
    console.log('=== find the middle value ===');
    var findMiddle = function(a, b, c) {
    var ret = c;
    if ((a-b)*(a-c) < 0) {
    ret = a;
    } else if ((b-a)*(b-c) < 0) {
    ret = b;
    }
    console.log('Result:', ret);
    })(1,-2,3);
    return ret;
    });

    (function(n) {
    console.log('=== decimal to binary ===');

    var dec2bin = function(n) {
    var ret = 0;
    var deci = 1;
    while (n) {
    var t = n%2;
    var t = n%2;
    t *= deci;
    deci *= 10;
    ret += t;
    n = Math.floor(n/2);
    }
    return ret;
    };

    console.log('Result:', ret);
    })(9);

    (function(x) {
    console.log('=== binary search ===');
    var binarySearch = function(x) {
    var ret;
    var a = [0,1,2,3,4,5,6,7,8,9,10];
    var l = 0;
    @@ -253,14 +263,12 @@ Array.prototype.swap = function(a, b) {
    break;
    }
    }
    return ret;
    };

    console.log('Result:', ret);
    })(8);

    // Sorting Ref: http://en.wikipedia.org/wiki/Sorting_algorithm
    (function(a) {
    console.log('=== bubble sort (swap sort) ===');

    // aka. swap sort
    var bubbleSort = function(a) {
    var fin = false;
    for (var i = a.length-1; i > 0; --i) { // n-1 round
    fin = true;
    @@ -274,13 +282,10 @@ Array.prototype.swap = function(a, b) {
    break;
    }
    }
    };

    console.log('Result:', a);
    })([8,5,3,1,4,2,9,0,7,6,8,5,3,1,4,2,9,0,7,6]);

    (function(a) {
    console.log('=== selection sort ===');

    var selectionSort = function(a) {
    for (var i = 0; i != a.length-1; ++i) {
    var t = i; // min pos
    // select minium to front
    @@ -291,13 +296,10 @@ Array.prototype.swap = function(a, b) {
    }
    a.swap(i, t);
    }
    };

    console.log('Result:', a);
    })([8,5,3,1,4,2,9,0,7,6,8,5,3,1,4,2,9,0,7,6]);

    (function(a) {
    console.log('=== insertion sort ===');

    var insertionSort = function(a) {
    for (var i = 1; i != a.length; ++i) {
    var t = a[i];
    // insert current a[i] to front proper pos
    @@ -310,13 +312,11 @@ Array.prototype.swap = function(a, b) {
    }
    a[j] = t;
    }
    };

    console.log('Result:', a);
    })([8,5,3,1,4,2,9,0,7,6,8,5,3,1,4,2,9,0,7,6]);

    (function(a) {
    console.log('=== shell sort (grouped insertion sort) ===');

    // aka. grouped insertion sort
    var shellSort = function(a) {
    var d = Math.floor(a.length/2);
    while (d) {
    // insertion sort by d
    @@ -335,13 +335,10 @@ Array.prototype.swap = function(a, b) {

    d = Math.floor(d/2);
    }
    };

    console.log('Result:', a);
    })([8,5,3,1,4,2,9,0,7,6,8,5,3,1,4,2,9,0,7,6]);

    (function(a) {
    console.log('=== merge sort ===');

    var mergeSort = function(a) {
    var merge = function(l, m, r) {
    var ret = [];
    var x = l;
    @@ -384,12 +381,10 @@ Array.prototype.swap = function(a, b) {
    }

    sort(0, a.length-1);
    console.log('Result:', a);
    })([8,5,3,1,4,2,9,0,7,6,8,5,3,1,4,2,9,0,7,6]);
    };

    (function(a) {
    console.log('=== quick sort ===');

    var quickSortFirst = function(a) {
    var qs = function(l, r) {
    if (l < r) {
    var m = l; // m is the last smaller element pos (swapable)
    @@ -402,18 +397,14 @@ Array.prototype.swap = function(a, b) {
    a.swap(l ,m); // put to middle
    qs(l, m-1); // sort left
    qs(m+1, r); // sort right
    }
    }
    };

    qs(0, a.length-1);

    console.log('Result:', a);
    })([8,5,3,1,4,2,9,0,7,6,8,5,3,1,4,2,9,0,7,6]);

    qs(0, a.length-1);
    };

    (function(a) {
    console.log('=== quick sort 2 ===');

    var quickSortLast = function(a) {
    var qs = function(l, r) {
    if (l < r) {
    var m = l; // m is the first bigger element pos (swapable)
    @@ -426,17 +417,14 @@ Array.prototype.swap = function(a, b) {
    a.swap(r ,m); // put to middle
    qs(l, m-1); // sort left
    qs(m+1, r); // sort right
    }
    }
    };

    qs(0, a.length-1);

    console.log('Result:', a);
    })([8,5,3,1,4,2,9,0,7,6,8,5,3,1,4,2,9,0,7,6]);
    qs(0, a.length-1);
    };

    (function(a) {
    console.log('=== heap sort ===');

    var heapSort = function(a) {
    var shiftup = function(l, r) {
    var j = r;
    while (true) {
    @@ -448,7 +436,7 @@ Array.prototype.swap = function(a, b) {
    var p = Math.floor((j-1)/2); // father
    if (a[p] >= a[j]) {
    break;
    }
    }
    a.swap(p, j);
    j = p;
    }
    @@ -462,15 +450,15 @@ Array.prototype.swap = function(a, b) {

    var shiftdown = function(l, r) {
    var j = l;
    while (true) {
    while (true) {
    var p = 2*j+1; // left child
    if (p >= r) {
    break;
    }

    // find the bigger child
    if (p+1 <= r && a[p+1] > a[p]) {
    ++p;
    ++p;
    }
    if (a[j] >= a[p]) { // j is already the biggest among the three
    break;
    @@ -486,13 +474,12 @@ Array.prototype.swap = function(a, b) {
    // shift first(top) down
    shiftdown(0, i-1);
    }
    };

    console.log('Result:', a);
    })([8,5,3,1,4,2,9,0,7,6,8,5,3,1,4,2,9,0,7,6]);

    (function(a) {
    console.log('=== radix sort ===');

    // aka. bucket sort
    var radixSort = function(a) {
    // use LSD
    var d = 1;
    // get Nth digit
    var dig = function(n, i) {
    @@ -531,6 +518,165 @@ Array.prototype.swap = function(a, b) {
    ++d;
    }

    return a;
    };


    // TODO: need fix!
    var radixStrSort = function(a) {
    // use MSD, recursive forward
    var d = 0;
    var rss = function(a, d) {
    var b = [];
    for (var i = 0; i != a.length; ++i) {
    // get d-th char
    var j = 0;
    if (d < a[i].length) {
    j = a[i][d].charCodeAt();
    }

    if (b[j] == undefined) {
    b[j] = [];
    }
    b[j].push(a[i]);
    }

    a = [];
    for (var k = 0; k != b.length; ++k) {
    // redo if more than 1
    if (b[k].length > 1) {
    rss(b[k], d+1);
    }

    // collect
    if (b[k] != undefined) {
    a = a.concat(b[k]);
    }
    }
    }
    return a;
    };


    // test main
    (function() {
    var ret, a;

    console.log('=== find same elements ===');
    ret = findSameElements([1,2,3,4,5,7,9,10], [3,4,7,10,12,13]);
    console.log('Result:', ret);

    console.log('=== fibonacci recursive ===');
    for (var i = 0; i <= 10; ++i) {
    console.log(fibonacci(i));
    }

    console.log('=== find 2nd max ===');
    ret = find2ndMax([7,-6,7,7,7]);
    console.log('Result:', ret);

    console.log('=== max subsequence sum ===');
    ret = maxSubseqSum([-2,11,-4,13,-5,-2,8]);
    console.log('Result:', ret);

    console.log('=== all arranges ===');
    allRanges([1,2,3,4]);

    console.log('=== Greatest Common Divisor & Least Common Multiple ===');
    gcdAndLcm(6, 9);

    console.log('=== matrix radio ===');
    matrixRadio(9);

    console.log('=== matrix round ===');
    ret = matrixRound(9);
    for (var i = 0; i != 9; ++i) {
    console.log(ret[i]);
    }

    console.log('=== star & dot ===');
    starDot(9);

    console.log('=== is primer ===');
    ret = isPrimer(437);
    console.log('Result:', ret);

    console.log('=== josephus ===');
    josephus(3);

    console.log('=== find the middle value ===');
    ret = findMiddle(1,-2,3);
    console.log('Result:', ret);

    console.log('=== decimal to binary ===');
    ret = dec2bin(9);
    console.log('Result:', ret);

    console.log('=== binary search ===');
    ret = binarySearch(8);
    console.log('Result:', ret);

    // Sorting Ref: http://en.wikipedia.org/wiki/Sorting_algorithm
    console.log('=== bubble sort ===');
    a = produceRamdomArray(100, 2);
    bubbleSort(a);
    checkSort(a);
    console.log('Result:', a);

    console.log('=== selection sort ===');
    a = produceRamdomArray(100, 2);
    selectionSort(a);
    checkSort(a);
    console.log('Result:', a);

    console.log('=== insertion sort ===');
    a = produceRamdomArray(100, 2);
    insertionSort(a);
    checkSort(a);
    console.log('Result:', a);

    console.log('=== shell sort ===');
    a = produceRamdomArray(100, 2);
    shellSort(a);
    checkSort(a);
    console.log('Result:', a);
    })([2138,345,523,1461,4,62,559,660,24357,624,85,52,3423,145,4425,245,94,60,74,645,99]);

    console.log('=== merge sort ===');
    a = produceRamdomArray(100, 2);
    mergeSort(a);
    checkSort(a);
    console.log('Result:', a);

    console.log('=== quick sort first ===');
    a = produceRamdomArray(100, 2);
    quickSortFirst(a);
    checkSort(a);
    console.log('Result:', a);

    console.log('=== quick sort last ===');
    a = produceRamdomArray(100, 2);
    quickSortLast(a);
    checkSort(a);
    console.log('Result:', a);

    console.log('=== heap sort ===');
    a = produceRamdomArray(100, 2);
    heapSort(a);
    checkSort(a);
    console.log('Result:', a);

    console.log('=== radix sort ===');
    a = produceRamdomArray(1000, 6);
    a = radixSort(a);
    checkSort(a);
    console.log('Result:', a);

    console.log('=== radix string sort ===');
    a = produceRamdomStrArray(6, 3);
    a = radixStrSort(a);
    checkSort(a);
    console.log('Result:', a);
    })();



  6. killwing revised this gist Mar 14, 2012. 1 changed file with 45 additions and 0 deletions.
    45 changes: 45 additions & 0 deletions algorithm.js
    View file
    Original file line number Diff line number Diff line change
    @@ -489,3 +489,48 @@ Array.prototype.swap = function(a, b) {

    console.log('Result:', a);
    })([8,5,3,1,4,2,9,0,7,6,8,5,3,1,4,2,9,0,7,6]);

    (function(a) {
    console.log('=== radix sort ===');

    var d = 1;
    // get Nth digit
    var dig = function(n, i) {
    var ret = 0;
    while (i--) {
    ret = n%10;
    n = Math.floor(n/10);
    }
    return ret;
    };

    while (true) {
    var b = [];
    var go = 0;

    for (var i = 0; i != a.length; ++i) {
    var j = dig(a[i], d);
    if (b[j] == undefined) {
    b[j] = [];
    }
    b[j].push(a[i]);
    go = go || j;
    }

    if (!go) {
    break;
    }

    // collect
    a = [];
    for (var k = 0; k != b.length; ++k) {
    if (b[k] != undefined) {
    a = a.concat(b[k]);
    }
    }
    ++d;
    }

    console.log('Result:', a);
    })([2138,345,523,1461,4,62,559,660,24357,624,85,52,3423,145,4425,245,94,60,74,645,99]);

  7. killwing revised this gist Mar 14, 2012. 1 changed file with 28 additions and 5 deletions.
    33 changes: 28 additions & 5 deletions algorithm.js
    View file
    Original file line number Diff line number Diff line change
    @@ -259,7 +259,7 @@ Array.prototype.swap = function(a, b) {

    // Sorting Ref: http://en.wikipedia.org/wiki/Sorting_algorithm
    (function(a) {
    console.log('=== bubble sort ===');
    console.log('=== bubble sort (swap sort) ===');

    var fin = false;
    for (var i = a.length-1; i > 0; --i) { // n-1 round
    @@ -300,7 +300,7 @@ Array.prototype.swap = function(a, b) {

    for (var i = 1; i != a.length; ++i) {
    var t = a[i];
    // insert current to proper pos
    // insert current a[i] to front proper pos
    for (var j = i; j > 0; --j) {
    if (a[j-1] > t) {
    a[j] = a[j-1];
    @@ -393,13 +393,13 @@ Array.prototype.swap = function(a, b) {
    var qs = function(l, r) {
    if (l < r) {
    var m = l; // m is the last smaller element pos (swapable)
    for (var i = l+1; i <= r; ++i) { // move smalls to front
    if (a[i] < a[l]) { // take a[l] as the middle value to divide
    for (var i = l+1; i <= r; ++i) {
    if (a[i] < a[l]) { // take first a[l] as the middle value to divide
    ++m;
    a.swap(i, m);
    }
    }
    a.swap(l ,m); // smalls a[l] bigs
    a.swap(l ,m); // put to middle
    qs(l, m-1); // sort left
    qs(m+1, r); // sort right
    }
    @@ -411,6 +411,29 @@ Array.prototype.swap = function(a, b) {
    })([8,5,3,1,4,2,9,0,7,6,8,5,3,1,4,2,9,0,7,6]);


    (function(a) {
    console.log('=== quick sort 2 ===');

    var qs = function(l, r) {
    if (l < r) {
    var m = l; // m is the first bigger element pos (swapable)
    for (var i = l; i <= r-1; ++i) {
    if (a[i] < a[r]) { // take last a[r] as the middle value to divide
    a.swap(i, m);
    ++m;
    }
    }
    a.swap(r ,m); // put to middle
    qs(l, m-1); // sort left
    qs(m+1, r); // sort right
    }
    };

    qs(0, a.length-1);

    console.log('Result:', a);
    })([8,5,3,1,4,2,9,0,7,6,8,5,3,1,4,2,9,0,7,6]);

    (function(a) {
    console.log('=== heap sort ===');

  8. killwing revised this gist Jul 3, 2011. 1 changed file with 48 additions and 0 deletions.
    48 changes: 48 additions & 0 deletions algorithm.js
    View file
    Original file line number Diff line number Diff line change
    @@ -339,6 +339,54 @@ Array.prototype.swap = function(a, b) {
    console.log('Result:', a);
    })([8,5,3,1,4,2,9,0,7,6,8,5,3,1,4,2,9,0,7,6]);

    (function(a) {
    console.log('=== merge sort ===');

    var merge = function(l, m, r) {
    var ret = [];
    var x = l;
    var y = m + 1;
    while (x <= m && y <= r) {
    if (a[x] <= a[y]) {
    ret.push(a[x]);
    ++x;
    } else {
    ret.push(a[y]);
    ++y;
    }
    }

    // concat left
    if (x > m) {
    ret = ret.concat(a.slice(y, r+1));
    } else { // y > r
    ret = ret.concat(a.slice(x, m+1));
    }

    // copy the result back
    var j = 0;
    for (var i = l; i <= r; ++i) {
    a[i] = ret[j++];
    }

    if (j != ret.length) {
    console.log('Error', ret);
    }
    }

    var sort = function(l, r) {
    if (l < r) {
    var m = Math.floor((l+r)/2);
    sort(l, m);
    sort(m+1, r);
    merge(l, m, r);
    }
    }

    sort(0, a.length-1);
    console.log('Result:', a);
    })([8,5,3,1,4,2,9,0,7,6,8,5,3,1,4,2,9,0,7,6]);

    (function(a) {
    console.log('=== quick sort ===');

  9. killwing revised this gist Jul 1, 2011. 1 changed file with 102 additions and 0 deletions.
    102 changes: 102 additions & 0 deletions algorithm.js
    View file
    Original file line number Diff line number Diff line change
    @@ -236,7 +236,109 @@ Array.prototype.swap = function(a, b) {
    console.log('Result:', ret);
    })(9);

    (function(x) {
    console.log('=== binary search ===');
    var ret;
    var a = [0,1,2,3,4,5,6,7,8,9,10];
    var l = 0;
    var r = a.length-1;
    while (l <= r) {
    var t = Math.floor((l+r)/2);
    if (x > a[t]) {
    l = t + 1;
    } else if (x < a[t]) {
    r = t - 1;
    } else {
    ret = t;
    break;
    }
    }

    console.log('Result:', ret);
    })(8);

    // Sorting Ref: http://en.wikipedia.org/wiki/Sorting_algorithm
    (function(a) {
    console.log('=== bubble sort ===');

    var fin = false;
    for (var i = a.length-1; i > 0; --i) { // n-1 round
    fin = true;
    for (var j = 0; j != i; ++j) {
    if (a[j] > a[j+1]) {
    a.swap(j, j+1);
    fin = false;
    }
    }
    if (fin) { // already all sorted
    break;
    }
    }

    console.log('Result:', a);
    })([8,5,3,1,4,2,9,0,7,6,8,5,3,1,4,2,9,0,7,6]);

    (function(a) {
    console.log('=== selection sort ===');

    for (var i = 0; i != a.length-1; ++i) {
    var t = i; // min pos
    // select minium to front
    for (var j = i+1; j != a.length; ++j) {
    if (a[j] < a[t]) {
    t = j;
    }
    }
    a.swap(i, t);
    }

    console.log('Result:', a);
    })([8,5,3,1,4,2,9,0,7,6,8,5,3,1,4,2,9,0,7,6]);

    (function(a) {
    console.log('=== insertion sort ===');

    for (var i = 1; i != a.length; ++i) {
    var t = a[i];
    // insert current to proper pos
    for (var j = i; j > 0; --j) {
    if (a[j-1] > t) {
    a[j] = a[j-1];
    } else {
    break;
    }
    }
    a[j] = t;
    }

    console.log('Result:', a);
    })([8,5,3,1,4,2,9,0,7,6,8,5,3,1,4,2,9,0,7,6]);

    (function(a) {
    console.log('=== shell sort (grouped insertion sort) ===');

    var d = Math.floor(a.length/2);
    while (d) {
    // insertion sort by d
    for (var i = d; i != a.length; ++i) {
    var t = a[i];
    // insert current to proper pos
    for (var j = i; j >= d; j -= d) {
    if (a[j-d] > t) {
    a[j] = a[j-d];
    } else {
    break;
    }
    }
    a[j] = t;
    }

    d = Math.floor(d/2);
    }

    console.log('Result:', a);
    })([8,5,3,1,4,2,9,0,7,6,8,5,3,1,4,2,9,0,7,6]);

    (function(a) {
    console.log('=== quick sort ===');

  10. killwing revised this gist Jun 30, 2011. 1 changed file with 11 additions and 11 deletions.
    22 changes: 11 additions & 11 deletions algorithm.js
    View file
    Original file line number Diff line number Diff line change
    @@ -135,24 +135,24 @@ Array.prototype.swap = function(a, b) {
    }


    var round = 0;
    var m=1;
    while(m <= n*n) {
    var round = 0;
    var m=1;
    while(m <= n*n) {
    for (var i=round; i<=n-round-1; ++i) {
    a[round][i] = m++;
    a[round][i] = m++;
    }
    for (var i=round+1; i<=n-round-1; ++i) {
    a[i][n-round-1] = m++;
    a[i][n-round-1] = m++;
    }
    for (var i=n-round-2; i>=round; --i) {
    a[n-round-1][i] = m++;
    a[n-round-1][i] = m++;
    }
    for (var i=n-round-2; i>=round+1; --i) {
    a[i][round] = m++;
    a[i][round] = m++;
    }
    round++;
    }
    round++;
    }

    for (var i = 0; i != n; ++i) {
    console.log(a[i]);
    @@ -165,14 +165,14 @@ Array.prototype.swap = function(a, b) {

    var ret = false;
    if (n%2 != 0) {
    ret = true;
    for (var i = 3; i*i <= n; i += 2) {
    if (n%i == 0) {
    ret = false;
    console.log('can be dived by', i);
    break;
    }
    }
    ret = (i*i > n);
    }

    console.log('Result:', ret);
  11. killwing revised this gist Jun 30, 2011. 1 changed file with 166 additions and 4 deletions.
    170 changes: 166 additions & 4 deletions algorithm.js
    100644 → 100755
    View file
    Original file line number Diff line number Diff line change
    @@ -1,6 +1,9 @@
    #!/usr/local/bin/node

    Array.prototype.swap = function(a, b) {
    if (a == b) {
    return;
    }
    var tmp = this[a];
    this[a] = this[b];
    this[b] = tmp;
    @@ -45,7 +48,7 @@ Array.prototype.swap = function(a, b) {
    var max = a[0];
    var secMax = Number.NEGATIVE_INFINITY;

    for (var i in a) {
    for (var i = 0; i != a.length; ++i) {
    if (a[i] > max) {
    secMax = max;
    max = a[i];
    @@ -55,14 +58,14 @@ Array.prototype.swap = function(a, b) {
    }

    console.log('Result:', secMax);
    })([7,-6,7,0,7]);
    })([7,-6,7,7,7]);


    (function(a) {
    console.log('=== max subsequence sum ===');
    var thisSum = 0;
    var maxSum = 0;
    for (var i in a) {
    for (var i = 0; i != a.length; ++i) {
    thisSum += a[i];
    if (thisSum > maxSum) {
    maxSum = thisSum;
    @@ -74,6 +77,165 @@ Array.prototype.swap = function(a, b) {
    console.log('Result:', maxSum);
    })([-2,11,-4,13,-5,-2,8]);

    (function(a) {
    console.log('=== all arranges ===');

    var exchange = function(l, r) {
    if (l == r) {
    console.log(a);
    return;
    }
    // exchange every elem to first position once
    for (var i = l; i <= r; ++i) {
    a.swap(l, i);
    exchange(l+1, r);
    a.swap(l, i);
    }
    };

    exchange(0, a.length-1);

    })([1,2,3,4]);

    (function(a, b) {
    console.log('=== Greatest Common Divisor & Least Common Multiple ===');

    var c = a * b;

    while (b) {
    var temp = b;
    b = a % b;
    a = temp;
    }

    console.log('GCD:', a);
    console.log('LCM:', c/a);

    })(6,9);

    (function(n) {
    console.log('=== matrix radio ===');

    for (var i = 0; i < 2*n-1; ++i) {
    for (var j = 0; j < 2*n-1; ++j) {
    var x = Math.abs(n-1-i);
    var y = Math.abs(n-1-j);
    process.stdout.write((n-(x>=y?x:y)).toString());
    }
    process.stdout.write('\n');
    }
    })(9);

    (function(n) {
    console.log('=== matrix round ===');
    // init arrays
    a = [];
    for (var i = 0; i != n; ++i) {
    a[i] = [];
    }


    var round = 0;
    var m=1;

    while(m <= n*n) {
    for (var i=round; i<=n-round-1; ++i) {
    a[round][i] = m++;
    }
    for (var i=round+1; i<=n-round-1; ++i) {
    a[i][n-round-1] = m++;
    }
    for (var i=n-round-2; i>=round; --i) {
    a[n-round-1][i] = m++;
    }
    for (var i=n-round-2; i>=round+1; --i) {
    a[i][round] = m++;
    }
    round++;
    }

    for (var i = 0; i != n; ++i) {
    console.log(a[i]);
    }

    })(9);

    (function(n) {
    console.log('=== is primer ===');

    var ret = false;
    if (n%2 != 0) {
    for (var i = 3; i*i <= n; i += 2) {
    if (n%i == 0) {
    ret = false;
    console.log('can be dived by', i);
    break;
    }
    }
    ret = (i*i > n);
    }

    console.log('Result:', ret);

    })(437);

    (function(n) {
    console.log('=== star & dot ===');
    for (var i = 0; i != n; ++i) {
    for (var j = 0; j != i; ++j) {
    process.stdout.write('*');
    for (var k = 0; k != i; ++k) {
    process.stdout.write('.');
    }
    }
    process.stdout.write('\n');
    }
    })(9);

    (function(interval) {
    console.log('=== josephus ===');
    var a = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1];
    var index = -1;
    for (var i = 0; i != a.length; ++i) {
    for (var j = 0; j != interval;) { // count interval
    index = (index+1)%a.length; // move forward
    if (a[index] != 0) { // skip the outed
    ++j;
    }
    }
    a[index] = 0; // kick out
    console.log(a);
    }

    })(3);

    (function(a, b, c) {
    console.log('=== find the middle value ===');
    var ret = c;
    if ((a-b)*(a-c) < 0) {
    ret = a;
    } else if ((b-a)*(b-c) < 0) {
    ret = b;
    }
    console.log('Result:', ret);
    })(1,-2,3);

    (function(n) {
    console.log('=== decimal to binary ===');

    var ret = 0;
    var deci = 1;
    while (n) {
    var t = n%2;
    t *= deci;
    deci *= 10;
    ret += t;
    n = Math.floor(n/2);
    }

    console.log('Result:', ret);
    })(9);

    // Sorting Ref: http://en.wikipedia.org/wiki/Sorting_algorithm
    (function(a) {
    console.log('=== quick sort ===');
    @@ -91,7 +253,7 @@ Array.prototype.swap = function(a, b) {
    qs(l, m-1); // sort left
    qs(m+1, r); // sort right
    }
    }
    };

    qs(0, a.length-1);

  12. kelviN created this gist Jun 30, 2011.
    156 changes: 156 additions & 0 deletions algorithm.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,156 @@
    #!/usr/local/bin/node

    Array.prototype.swap = function(a, b) {
    var tmp = this[a];
    this[a] = this[b];
    this[b] = tmp;
    };

    (function(a, b) {
    console.log('=== find same elements ===');
    var ret = [];
    var i = 0;
    var j = 0;

    while (i < a.length && j < b.length) {
    if (a[i] < b[j]) {
    ++i;
    } else if (a[i] > b[j]) {
    ++j;
    } else { // a[i] == b[j]
    ret.push(a[i]);
    ++i;
    ++j;
    }
    }

    console.log('Result:', ret);
    })([1,2,3,4,5,7,9,10], [3,4,7,10,12,13]);


    (function(n) {
    console.log('=== fibonacci recursive ===');
    var fib = function(n) {
    return (n == 0 || n == 1) ? n : fib(n-1) + fib(n-2);
    };

    for (var i = 0; i <= n; ++i) {
    console.log(fib(i));
    }
    })(10);


    (function(a) {
    console.log('=== find 2nd max ===');
    var max = a[0];
    var secMax = Number.NEGATIVE_INFINITY;

    for (var i in a) {
    if (a[i] > max) {
    secMax = max;
    max = a[i];
    } else if (a[i] < max && a[i] > secMax) {
    secMax = a[i];
    }
    }

    console.log('Result:', secMax);
    })([7,-6,7,0,7]);


    (function(a) {
    console.log('=== max subsequence sum ===');
    var thisSum = 0;
    var maxSum = 0;
    for (var i in a) {
    thisSum += a[i];
    if (thisSum > maxSum) {
    maxSum = thisSum;
    } else if (thisSum < 0) { // reset to 0
    thisSum = 0;
    }
    }

    console.log('Result:', maxSum);
    })([-2,11,-4,13,-5,-2,8]);

    // Sorting Ref: http://en.wikipedia.org/wiki/Sorting_algorithm
    (function(a) {
    console.log('=== quick sort ===');

    var qs = function(l, r) {
    if (l < r) {
    var m = l; // m is the last smaller element pos (swapable)
    for (var i = l+1; i <= r; ++i) { // move smalls to front
    if (a[i] < a[l]) { // take a[l] as the middle value to divide
    ++m;
    a.swap(i, m);
    }
    }
    a.swap(l ,m); // smalls a[l] bigs
    qs(l, m-1); // sort left
    qs(m+1, r); // sort right
    }
    }

    qs(0, a.length-1);

    console.log('Result:', a);
    })([8,5,3,1,4,2,9,0,7,6,8,5,3,1,4,2,9,0,7,6]);


    (function(a) {
    console.log('=== heap sort ===');

    var shiftup = function(l, r) {
    var j = r;
    while (true) {
    if (j <= l) {
    break;
    }

    // the larger the upper
    var p = Math.floor((j-1)/2); // father
    if (a[p] >= a[j]) {
    break;
    }
    a.swap(p, j);
    j = p;
    }
    };

    // build the max heap
    for (var i = 1; i < a.length; ++i) {
    // shift the last up
    shiftup(0, i);
    }

    var shiftdown = function(l, r) {
    var j = l;
    while (true) {
    var p = 2*j+1; // left child
    if (p >= r) {
    break;
    }

    // find the bigger child
    if (p+1 <= r && a[p+1] > a[p]) {
    ++p;
    }
    if (a[j] >= a[p]) { // j is already the biggest among the three
    break;
    }
    a.swap(p, j);
    j = p;
    }
    };

    // find max every time and rebuild heap
    for (var i = a.length-1; i > 0; --i) {
    a.swap(0, i); // swap the max to last
    // shift first(top) down
    shiftdown(0, i-1);
    }

    console.log('Result:', a);
    })([8,5,3,1,4,2,9,0,7,6,8,5,3,1,4,2,9,0,7,6]);