【アルゴリズムの勉強】Rubyでハッシュ法を使用せずデータの追加を行う

Ruby アルゴリズム

概要

ハッシュ法を使用せず昇順にソートされた状態のデータに新しい値の追加を行う。
バイナリサーチのアルゴリズムを用いて挿入すべき位置を見つけ値を追加し、それ以降の全要素を一つずつ後方へ移動するため、ハッシュ法を用いたデータの追加と比べ効率は悪い。

Rubyで実装

original_data = [1, 3, 5, 6, 8, 10, 12, 13, 15, 17, 20, 24, 30]

def add_data(value, asc_sorted_data)
  number_of_elements = asc_sorted_data.count
  insert_location = get_insert_location(value, asc_sorted_data, number_of_elements)
  if insert_location == -1
    puts "#{value}は既に追加済みです"
    return asc_sorted_data
  end
  while insert_location <= number_of_elements
    original_value = asc_sorted_data[insert_location]
    asc_sorted_data[insert_location] = value
    value = original_value
    insert_location += 1
  end
  return asc_sorted_data
end

def get_insert_location(target, asc_sorted_data, number_of_elements)
  left = 0
  right = number_of_elements - 1

  # バイナリサーチのアルゴリズムを使用
  while left <= right
    center = (left + right) / 2
    return -1 if asc_sorted_data[center] == target
    if asc_sorted_data[center - 1] < target && asc_sorted_data[center] > target
      break
    end
    if asc_sorted_data[center] < target
      left = center + 1
    else
      right = center - 1
    end
  end
  if center == (number_of_elements - 1) && asc_sorted_data[center] < target
    insert_location = center + 1
  else
    insert_location = center
  end

  return insert_location
end

p original_data
# => [1, 3, 5, 6, 8, 10, 12, 13, 15, 17, 20, 24, 30]
data = add_data(11, original_data)
p data
# => [1, 3, 5, 6, 8, 10, 11, 12, 13, 15, 17, 20, 24, 30]

参考文献、参考リンク