2015年1月10日土曜日

150110(3)

Ruby


「アルゴリズムとデータ構造」のRuby版。

マージソート

# -*- coding: cp932 -*-

# データの件数
N = 10

def mergeSort(n, x, offset)
  return if n <= 1
  m = n / 2
  # ブロックを2分割する
  mergeSort(m, x, offset)
  mergeSort(n - m, x, offset + m)
  # 併合操作
  buffer = Array.new(m)
  for i in (0..m - 1)
    buffer[i] = x[offset + i]
  end
  j = m
  i = 0
  k = 0
  while i < m && j < n
    if buffer[i] <= x[offset + j]
      x[offset + k] = buffer[i]
      i += 1
    else
      x[offset + k] = x[offset + j]
      j += 1
    end
      k += 1
  end
  while i < m
    x[offset + k] = buffer[i]
    k += 1
    i += 1
  end
end

@sort = []
printf("ソート準備:\n")
for i in (0..N - 1)
  # 配列にランダムな値を格納
  @sort[i] = rand(1000)
  printf("%d ", @sort[i])
end
printf("\nソート開始:\n")
mergeSort(N, @sort, 0)
printf("\nソート終了:\n")
for i in (0..N - 1)
  printf("%d ", @sort[i])
end

0 件のコメント:

コメントを投稿