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