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
[algorithm] various algorithm samples
Raw
algorithm.js
#!/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;
};
(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 = 0; i != a.length; ++i) {
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,7,7]);
(function(a) {
console.log('=== max subsequence sum ===');
var thisSum = 0;
var maxSum = 0;
for (var i = 0; i != a.length; ++i) {
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]);
(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) {
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;
}
}
}
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);
(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 (swap 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 a[i] to front 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('=== 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 ===');
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) {
if (a[i] < a[l]) { // take first a[l] as the middle value to divide
++m;
a.swap(i, m);
}
}
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]);
(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 ===');
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]);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment