nikezono · May 14, 2013 11:21
diff --git a/bogosort.coffee b/bogosort.coffee
 sample = require './sample.json'
 ###
 Bogosort
 「無作為に数列を並べて、ソートができていれば終わり」
 停止性は無限の猿定理により保証される
 無限の猿定理:
 ランダムに文字列を作り続ければ、
 どんな文字列もいつかはできあがるという定理
 ###

 master = sample.slice(0)
 #正答を用意
 quick = sample.sort (a,b)->
  return (a-b)

 #無作為に並べてquickと一致したら終わり
 while master isnt quick
  master.sort (a,b) ->
    Math.random() - Math.random()
diff --git a/bozosort.coffee b/bozosort.coffee
 sample = require './sample.json'
 ###
 Bozosort
 「数列がソートできていなければ、ランダムに二つの要素を入れ替える」
 ###

 master = sample.slice(0)
 #正答を用意
 quick = sample.sort (a,b)->
  return (a-b)

 #無作為に並べてquickと一致したら終わり
 while master isnt quick
  rand = Math.floor(Math.random() * quick.length)
  rand2 = Math.floor(Math.random() * quick.length)
  cache = master[rand]
  master[rand] = master[rand2]
  master[rand2] = cache
diff --git a/mergesort.coffee b/mergesort.coffee
 sample = require './sample.json'
 ###
 Mergesort
 分割統治法を用いて、要素数が２になるまで配列を分割し続ける
 それぞれの子配列をソートしてマージしていく
 node.jsだとasyncなのでうまくいってない
 ###
 sorted = []

 merge = (array) ->
  return array if array.length < 2 #0&1
  mid = Math.ceil array.length/2
  left = merge array.slice(0,mid)
  right = merge array.slice(mid)
  until (left.length < 1 and right.length < 1)
    unless left[0]
      array.push right.shift()
    else unless right[0]
      array.push left.shift()
    else if left[0] < right[0] # 小さい方をpush
      array.push left.shift()
    else
      array.push right.shift()
  return array.concat(left, right)
 console.log merge sample
diff --git a/sample.json b/sample.json
 [ 138,
  20,
  199,
  171,
  193,
  77,
  137,
  185,
  109,
  103,
  103,
  171,
  176,
  131,
  119,
  141,
  141,
  170,
  99,
  28,
  107,
  9,
  54,
  47,
  70,
  65,
  35,
  59,
  118,
  55,
  51,
  101,
  28,
  17,
  73,
  163,
  3,
  170,
  30,
  22,
  148,
  68,
  107,
  127,
  145,
  82,
  89,
  67,
  112,
  31,
  182,
  191,
  102,
  197,
  109,
  152,
  141,
  93,
  180,
  134,
  116,
  175,
  37,
  26,
  83,
  101,
  56,
  44,
  48,
  27,
  59,
  196,
  79,
  65,
  68,
  102,
  71,
  146,
  35,
  9,
  37,
  145,
  105,
  59,
  145,
  6,
  125,
  29,
  30,
  93,
  9,
  192,
  39,
  150,
  5,
  174,
  176,
  163,
  53,
  197,
  172,
  104,
  187,
  168,
  143,
  125,
  71,
  15,
  165,
  16,
  90,
  79,
  24,
  167,
  22,
  163,
  162,
  154,
  191,
  36,
  181,
  184,
  2,
  132,
  195,
  97,
  148,
  197,
  168,
  163,
  56,
  103,
  155,
  140,
  38,
  152,
  116,
  88,
  130,
  153,
  6,
  38,
  4,
  133,
  11,
  122,
  60,
  120,
  169,
  78,
  101,
  92,
  62,
  149,
  180,
  126,
  96,
  197,
  75,
  161,
  140,
  189,
  124,
  131,
  140,
  173,
  26,
  20,
  60,
  168,
  102,
  42,
  115,
  189,
  191,
  84,
  7,
  10,
  172,
  78,
  63,
  182,
  190,
  54,
  187,
  132,
  141,
  95,
  115,
  175,
  176,
  61,
  56,
  131,
  107,
  108,
  72,
  126,
  175,
  84 ]
diff --git a/sleepsort.coffee b/sleepsort.coffee
 sample = require './sample.json'
 ###
 Sleepsort
 http://d.hatena.ne.jp/gfx/20110519/1305810786
 ソート対象の数値データを次々にsleepコマンドに渡し，
 sleepが終わった順に出力すると結果がソートされている
 というしくみ
 timeoutの時間をどれだけ取るかで速度が可変するという謎のソート
 node.jsは10ピコ秒まで分解能があるので理論的にはめっちゃ早い
 ###
 sorted = []

 sleep_sort = (a) ->
  callback = (n) ->
    setTimeout (->
      console.log n
      sorted.push n
    ), (n + 1) * 1e-8 #10ピコ秒= 1e-8 4msぐらいじゃないと自分の環境では安定しなかった
  i = 0
  while i < a.length
    callback a[i]
    i++

 #sleep_sort [0,23,5,11,3,4,5]
 sleep_sort(sample)
	sample = require './sample.json'
	###
	Bogosort
	「無作為に数列を並べて、ソートができていれば終わり」
	停止性は無限の猿定理により保証される
	無限の猿定理:
	ランダムに文字列を作り続ければ、
	どんな文字列もいつかはできあがるという定理
	###

	master = sample.slice(0)
	#正答を用意
	quick = sample.sort (a,b)->
	return (a-b)

	#無作為に並べてquickと一致したら終わり
	while master isnt quick
	master.sort (a,b) ->
	Math.random() - Math.random()
	sample = require './sample.json'
	###
	Bozosort
	「数列がソートできていなければ、ランダムに二つの要素を入れ替える」
	###

	master = sample.slice(0)
	#正答を用意
	quick = sample.sort (a,b)->
	return (a-b)

	#無作為に並べてquickと一致したら終わり
	while master isnt quick
	rand = Math.floor(Math.random() * quick.length)
	rand2 = Math.floor(Math.random() * quick.length)
	cache = master[rand]
	master[rand] = master[rand2]
	master[rand2] = cache
	sample = require './sample.json'
	###
	Mergesort
	分割統治法を用いて、要素数が２になるまで配列を分割し続ける
	それぞれの子配列をソートしてマージしていく
	node.jsだとasyncなのでうまくいってない
	###
	sorted = []

	merge = (array) ->
	return array if array.length < 2 #0&1
	mid = Math.ceil array.length/2
	left = merge array.slice(0,mid)
	right = merge array.slice(mid)
	until (left.length < 1 and right.length < 1)
	unless left[0]
	array.push right.shift()
	else unless right[0]
	array.push left.shift()
	else if left[0] < right[0] # 小さい方をpush
	array.push left.shift()
	else
	array.push right.shift()
	return array.concat(left, right)
	console.log merge sample
	[ 138,
	20,
	199,
	171,
	193,
	77,
	137,
	185,
	109,
	103,
	103,
	171,
	176,
	131,
	119,
	141,
	141,
	170,
	99,
	28,
	107,
	9,
	54,
	47,
	70,
	65,
	35,
	59,
	118,
	55,
	51,
	101,
	28,
	17,
	73,
	163,
	3,
	170,
	30,
	22,
	148,
	68,
	107,
	127,
	145,
	82,
	89,
	67,
	112,
	31,
	182,
	191,
	102,
	197,
	109,
	152,
	141,
	93,
	180,
	134,
	116,
	175,
	37,
	26,
	83,
	101,
	56,
	44,
	48,
	27,
	59,
	196,
	79,
	65,
	68,
	102,
	71,
	146,
	35,
	9,
	37,
	145,
	105,
	59,
	145,
	6,
	125,
	29,
	30,
	93,
	9,
	192,
	39,
	150,
	5,
	174,
	176,
	163,
	53,
	197,
	172,
	104,
	187,
	168,
	143,
	125,
	71,
	15,
	165,
	16,
	90,
	79,
	24,
	167,
	22,
	163,
	162,
	154,
	191,
	36,
	181,
	184,
	2,
	132,
	195,
	97,
	148,
	197,
	168,
	163,
	56,
	103,
	155,
	140,
	38,
	152,
	116,
	88,
	130,
	153,
	6,
	38,
	4,
	133,
	11,
	122,
	60,
	120,
	169,
	78,
	101,
	92,
	62,
	149,
	180,
	126,
	96,
	197,
	75,
	161,
	140,
	189,
	124,
	131,
	140,
	173,
	26,
	20,
	60,
	168,
	102,
	42,
	115,
	189,
	191,
	84,
	7,
	10,
	172,
	78,
	63,
	182,
	190,
	54,
	187,
	132,
	141,
	95,
	115,
	175,
	176,
	61,
	56,
	131,
	107,
	108,
	72,
	126,
	175,
	84 ]
	sample = require './sample.json'
	###
	Sleepsort
	http://d.hatena.ne.jp/gfx/20110519/1305810786
	ソート対象の数値データを次々にsleepコマンドに渡し，
	sleepが終わった順に出力すると結果がソートされている
	というしくみ
	timeoutの時間をどれだけ取るかで速度が可変するという謎のソート
	node.jsは10ピコ秒まで分解能があるので理論的にはめっちゃ早い
	###
	sorted = []

	sleep_sort = (a) ->
	callback = (n) ->
	setTimeout (->
	console.log n
	sorted.push n
	), (n + 1) * 1e-8 #10ピコ秒= 1e-8 4msぐらいじゃないと自分の環境では安定しなかった
	i = 0
	while i < a.length
	callback a[i]
	i++

	#sleep_sort [0,23,5,11,3,4,5]
	sleep_sort(sample)