アルゴリズムのキホン

アルゴリズムのキホン

「アルゴリズム」のキホン (イチバンやさしい理工系シリーズ)

「アルゴリズム」のキホン (イチバンやさしい理工系シリーズ)

第5章 並び換えと探索

Ruby の便利なメソッドを（なるべく）使わずに書いてみる。
わからなかったものもあり。

  • バケットソート
base = [8, 2, 1, 5, 9, 7]
max = 0
base.each { |v| max = v if max < v }
backet = Array.new(max) { nil }
base.each { |i| backet[i] = i }
p backet.compact
  • 基数ソート 毎回新しいバケットを作っているので意味が違うからダメか。
    combination くらいは使っても良いか。
base = %w(123 602 082 777 057 510 396 196 843 138)
bucket = base.combination(1).to_a

2.downto(0) do |i|
  tmp = bucket.dup
  bucket = Array.new(bucket.count) { [] }
  tmp.each do |ary|
    ary.each do |str|
      bucket[str[i].to_i].push str
    end
  end
end

p bucket.flatten
  • 単純選択法
boxes = [35, 80, 21, 54, 11, 45, 92, 39]
quantity = boxes.count

quantity.times do |i|
  min = boxes[i]
  nth = i
  boxes[i + 1...quantity].each_with_index do |v, idx|
    if min > v
      min = v
      nth = i + 1 + idx
    end
  end

  boxes.delete_at nth
  boxes.insert i, min
end

p boxes

boxes = [19, 80, 77, 11, 54]

(boxes.count - 1).downto(1) do |i|
  i.times do |j|
    next if boxes[j] < boxes[j + 1]
    tmp = boxes[j + 1]
    boxes[j + 1] = boxes[j]
    boxes[j] = tmp
  end
end

p boxes
  • 単純挿入法
boxes = [77, 19, 80, 79, 20, 11]

1.upto(boxes.count - 1) do |i|
  nth = nil
  target = boxes[i]
  boxes[0..i].each_with_index do |v, idx|
    next if target > v
    nth = idx
    break
  end

  next unless nth
  boxes.delete_at(i)
  boxes.insert nth, target
end

p boxes

def simple_sort(boxes)
  result = boxes.dup
  1.upto(result.count - 1) do |i|
    nth = nil
    target = result[i]
    result[0..i].each_with_index do |v, idx|
      next if target > v
      nth = idx
      break
    end

    next unless nth
    result.delete_at i
    result.insert nth, target
  end

  result
end

boxes = [77, 19, 80, 79, 20, 11, 98, 45, 21, 8, 32, 45]
quantity = boxes.count
distance = quantity

loop do
  distance /= 2
  tmp = Array.new(distance) { [] }
  distance.times do |i|
    nth = i
    loop do
      break if nth >= quantity
      tmp[i] << boxes[nth]
      nth += distance
    end
  end

  tmp.each_with_index { |ary, idx| tmp[idx] = simple_sort(ary) }

  boxes = []
  idx = 0
  loop do
    distance.times { |i| boxes << tmp[i][idx] if tmp[i][idx] }
    idx += 1
    break if boxes.count == quantity
  end

  break if distance <= 1
end

p boxes
  • 併合（マージ）
boxes = [
  [4, 5, 9, 14],
  [1, 3, 11],
  [2, 8, 12]
]

result = []
num = boxes.count

loop do
  min = nil
  nth = nil
  num.times do |i|
    v = boxes[i][0]
    next unless v
    if min.nil? || min > v
      min = v
      nth = i
    end
  end
  break unless nth
  result << boxes[nth].shift
end

p result

def merge_array(boxes)
  result = []
  num = boxes.count

  loop do
    min = nil
    nth = nil
    num.times do |i|
      v = boxes[i][0]
      next unless v
      if min.nil? || min > v
        min = v
        nth = i
      end
    end
    break unless nth
    result << boxes[nth].shift
  end
  result
end

base = [8, 2, 4, 12, 1, 9, 6, 3]
work = base.combination(1).to_a

loop do
  tmp = work
  work = []
  0.step(tmp.count - 1, 2) do |i|
    work << merge_array([tmp[i], tmp[i + 1] || []])
  end

  p work
  break if work.count == 1
end

p work.flatten