Skip to content

Instantly share code, notes, and snippets.

@kkeeth

kkeeth/bable_sort.js

Last active March 31, 2016 06:10
Show Gist options
  • Save kkeeth/4c817d0acc5acada6315 to your computer and use it in GitHub Desktop.
Save kkeeth/4c817d0acc5acada6315 to your computer and use it in GitHub Desktop.
Download ZIP
アルゴリズム勉強会用ソースコード
Raw
bable_sort.js
// データ初期化
var data = [2, 5, 3, 1, 9];
// バブルソート
var bable_sort = function (data) {
// データ入れ替え用一時変数
var tmp = 0;
// 最後の要素を除いて、すべての要素を並べ替えます
for (var i = 0; i < data.length - 1; i++) {
// 下から上に順番に比較します
for (var j = data.length - 1; j > i; j--) {
// 上の方が大きいときは互いに入れ替えます
if (data[j] < data[j - 1]) {
tmp = data[j];
data[j] = data[j - 1];
data[j - 1] = tmp;
}
}
}
return data;
};
// バブルソート実行
console.log(bable_sort(data));
Raw
bucket_sort.js
// データ初期化
var data = [2, 5, 3, 1, 9];
// バケットソート
var bucket_sort = function (data) {
// data個数分のバケツを用意
var bucket = new Array(data.length);
// すべてのデータを対応するバケツに投入
for (var i = 0; i < data.length; i++) {
bucket[data[i]] = data[i];
}
// data配列を初期化
var data = [];
//バケツの順番に中のデータを取りだし、配列に格納
for (var i = 0; i < bucket.length; i++) {
if (!isNaN(bucket[i])) {
data.push(Number(bucket[i]));
}
}
return data;
};
// バケットソート実行
console.log('bucket sort:' + bucket_sort(data));
Raw
dragon_curve.html
<!DOCTYPE html>
<html>
<head>
<title>Dragon Curve</title>
<style type="text/css">body {background-color: white;}</style>
</head>
<body>
<canvas id="canvas" height="600" width="800">
Unfortunately, your browser cannot display this page properly. It does not
support the HTML5 canvas element.
</canvas>
<script type="text/javascript">
var computeLeftPoint = function (startPoint, endPoint) {
return {
x: 0.5 * (endPoint.y - startPoint.y + endPoint.x + startPoint.x),
y: 0.5 * (endPoint.y + startPoint.y - endPoint.x + startPoint.x)
}
}
var computeRightPoint = function (startPoint, endPoint) {
return {
x: 0.5 * (-endPoint.y + startPoint.y + endPoint.x + startPoint.x),
y: 0.5 * ( endPoint.y + startPoint.y + endPoint.x - startPoint.x)
}
}
var lastElement = function (array) {
return array[array.length - 1]
}
var concatNewPoints = function (accumulator, endPoint) {
var rule = accumulator.alternator ? computeLeftPoint : computeRightPoint
var midPoint = rule(lastElement(accumulator.points), endPoint)
return {
points: accumulator.points.concat(midPoint, endPoint),
alternator: !accumulator.alternator
}
}
var evolveCurve = function (points) {
var firstPoint = points[0]
var endPoints = points.slice(1)
return endPoints.reduce(concatNewPoints,
{ points: [firstPoint], alternator: true }
).points
}
var generateCurve = function (n, points) {
if (n <= 0) {
return points
}
return evolveCurve(generateCurve(n-1, points))
}
var Renderer = function (canvas) {
this.canvas = canvas
}
Renderer.prototype.drawCurve = function (points) {
var context = canvas.getContext("2d")
context.strokeStyle = "skyblue"
context.beginPath()
context.moveTo(points[0].x, points[0].y)
points.forEach(function (point) {
context.lineTo(point.x, point.y)
})
context.stroke()
}
;(function () {
points = generateCurve(14, [
{ x: 150, y: 410 },
{ x: 600, y: 450 }
])
var renderer = new Renderer(document.getElementById("canvas"))
renderer.drawCurve(points)
}())
;
</script>
</body>
</html>
Raw
dragon_curve.js
// 文字列格納用
var str = 'a';
// 回数設定用
var times = 10;
var dragon_curve = function (n) {
if (n == 0) {
// 出力して終了
console.log(str);
}
else if (n == times) {
str += 'b';
dragon_curve(n - 1);
}
else {
str += str.split("").reverse().join("");
dragon_curve(n - 1);
}
};
// ドラゴンカーブ実行
dragon_curve(times);
Raw
heap_sort.js
// データ初期化
var data = [2, 5, 3, 1, 9];
// データ配列（ヒープ）
var heap = [];
// 現在の要素数
var num;
// 現在の着目ライン
var target;
// ヒープにデータ挿入
var insert = function (a) {
heap[num++] = a;
var i = num, j = i / 2;
while (i > 1 && heap[i - 1] < heap[j - 1]) {
var t = heap[i - 1];
heap[i - 1] = heap[j - 1];
heap[j - 1] = t;
i = j;
j = i / 2;
}
};
// ヒープから先頭の要素を取り除き、更新
var deletemin = function () {
var ret = heap[0];
// ヒープの更新
heap[0] = heap[--num];
var i = 1, j = i * 2;
while (j <= num) {
if (j + 1 <= num && heap[j - 1] > heap[j])
j++;
if (heap[i - 1] > heap[j - 1]) {
var t = heap[i - 1];
heap[i - 1] = heap[j - 1];
heap[j - 1] = t;
}
i = j;
j = i * 2;
}
return ret;
};
// ヒープソート
var heap_sort = function (arr) {
// 必要なヒープ用配列を確保
heap = new Array[arr.length];
num = 0;
// ヒープに要素を追加
for (target = 0; target < arr.length; target++) {
insert(arr[target]);
}
// ヒープから取り出しながら配列に格納します。
for (target = 0; num > 0; target++) {
arr[target] = deletemin();
}
};
// ヒープソート実行
console.log(heap_sort(data));
Raw
merge_sort.js
// データ初期化
var data = [2, 5, 3, 1, 9];
// マージ
var merge = function (arr_par1, arr_par2, arr_all) {
var i = 0;
var j = 0;
while (i < arr_par1.length || j < arr_par2.length) {
if (j >= arr_par2.length || (i < arr_par1.length && arr_par1[i] < arr_par2[j])) {
arr_all[i + j] = arr_par1[i];
i++;
}
else {
arr_all[i + j] = arr_par2[j];
j++;
}
}
};
// マージソート
var merge_sort = function (data) {
if (data.length > 1) {
var m = Math.floor(data.length / 2);
var n = data.length - m;
var arr_par1 = new Array(m);
var arr_par2 = new Array(n);
for (var i = 0; i < m; i++)
arr_par1[i] = data[i];
for (var i = 0; i < n; i++)
arr_par2[i] = data[m + i];
merge_sort(arr_par1);
merge_sort(arr_par2);
merge(arr_par1, arr_par2, data);
}
};
// マージソート実行
merge_sort(data);
console.log(data);
Raw
quick_sort.js
// データ初期化
var data = [2, 5, 3, 1, 9];
/**
* 軸の選択関数　その１
* 順に見て、最初に見つかった異なる2つの要素のうち、
* 大きいほうの番号を返す
*/
var pivot = function (data, i, j) {
var k = i + 1;
while (k <= j && data[i] == data[k]) {
k++;
}
if (k > j)
return -1;
if (data[i] >= data[k])
return i;
return k;
};
/**
* パーティション分割
* data[i]～data[j]の間で、x を軸として分割
* 軸より小さい要素は前に、大きい要素は後ろに移動
* 大きい要素の開始番号を返す
*/
var partition = function (arr, i, j, x) {
var l = i;
var r = j;
// 検索が交差するまで繰り返します
while (l <= r) {
// 軸要素以上のデータを探します
while (l <= j && arr[l] < x)
l++;
// 軸要素未満のデータを探します
while (r >= i && arr[r] >= x)
r--;
if (l > r)
break;
var t = arr[l];
arr[l] = arr[r];
arr[r] = t;
l++;
r--;
}
return l;
};
// クイックソート
var quick_sort = function (arr, i, j) {
if (i == j)
return;
var p = pivot(arr, i, j);
if (p != -1) {
var k = partition(arr, i, j, arr[p]);
quick_sort(arr, i, k - 1);
quick_sort(arr, k, j);
}
return arr;
};
// クイックソート実行
console.log(quick_sort(data, 0, data.length - 1));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment