クイックソートとバブルソートの比較

sort.coffee

# クイック
qSort = (ary) ->
  if ary.length <= 1
    return ary
  center = Math.floor (ary.length / 2)
  pivot = ary[center]
  left = []
  right = []
  for val in ary
    if val < pivot
      left.push val
    if val > pivot
      right.push val
  sLeft = qSort left
  sRight = qSort right

  [].concat sLeft, [pivot], sRight

# バブル
bSort = (ary) ->
  clone = ary.concat()
  change = true
  while change
    change = false
    n = 0
    for val, n in clone when clone[n + 1]?
      if clone[n] > clone[n + 1]
        change = true
        [clone[n], clone[n + 1]] = [clone[n + 1], clone[n]]
  clone

# ランダムな数列を返す
getShuffleArray = (len) ->
  base = [1..len]
  ret = []
  while base.length
    n = (Math.floor Math.random() * base.length)
    ret.push base[n]
    base.splice(n, 1)
  ret

check = (l = 10, n = 1000) ->
  console.log "---------------"
  console.log "配列の長さ : #{l}, 繰り返し : #{n}"

  expectation = [1..l].join(",")
  loops = [1..n]

  console.time "クイック"
  for n in loops
    console.assert expectation is (qSort getShuffleArray l).join(","), "だめ"
  console.timeEnd "クイック"

  console.time "バブル"
  for n in loops
    console.assert expectation is (bSort getShuffleArray l).join(","), "だめ"
  console.timeEnd "バブル"

check 1    , 1000
check 10   , 1000
check 100  , 1000
check 1000 , 1000