簡単なアルゴリズム問題を解いた【探索、ソート】

はじめに

キタミ式の基本情報技術者試験の勉強してたらアルゴリズムの説明が出てきたので、久しぶりにコーディングしてみた

一つのメソッドで完結させる、なるべく簡潔なコードにする、フラグ変数やインデックス変数を使わない、などの縛りを設けてます

※仕様は殆ど上記の本の内容だけに従ってます

※ハッシュ法、ヒープソートはわけわかめだったのでやってません
　似たような書き方されてるコードがあれば教えてください

探索

線形探索法

def linear_search(ary, find)
  ary.each { |x| return true if x == find }
  false
end

二分探索法

def binary_search(ary_should_sort, find)
  ary = ary_should_sort.sort

  loop do
    return false if ary.size == 1

    middle = ary[ary.size / 2]
    return true if middle == find

    half = ary.each_slice(ary.size / 2).to_a
    half[1].concat(half[2]) if half[2] != nil

    ary = middle > find ? half[0] : half[1]
  end
end

ソート

基本交換法（バブルソート）

def bubble_sort(copied_ary)
  ary = copied_ary.dup

  (ary.size).times do
    (ary.size - 1).times do |i|
      ary[i], ary[i + 1] = ary[i + 1], ary[i] if ary[i] > ary[i + 1]
    end
  end

  ary
end

終了判定(ary.each_cons(2).all? { |a, b| a <= b })があんまりよくない気がするけど本に何も書いてないのでセーフ
↑偶然バブルソートは配列の要素数回ループすると知ったので書き換えました

基本選択法（選択ソート）

def selection_sort(copied_ary)
  ary = copied_ary.dup

  (ary.size - 1).times do |i|
    min_index              = ary[i..].index(ary[i..].min) + i
    ary[i], ary[min_index] = ary[min_index], ary[i]
  end

  ary
end

基本挿入法（挿入ソート）

def insertion_sort(copied_ary)
  ary = copied_ary.dup

  divided_ary  = ary.chunk_while { |a, b| a <= b }.to_a
  sorted_ary   = divided_ary.max_by(&:size)
  unsorted_ary = (divided_ary - [sorted_ary]).flatten

  return sorted_ary if unsorted_ary == []

  unsorted_ary.each do |e_un|
    index = sorted_ary.size
    sorted_ary.reverse_each do |e|
      break unless e > e_un
      index -= 1
    end

    sorted_ary.insert(index, e_un)
  end

  sorted_ary
end

シェルソート

def shell_sort(copied_ary)
  ary = copied_ary.dup

  h = 1
  h = h * 3 + 1 until h > ary.size / 9

  while h != 0
    sliced_ary = ary.each_slice(h).to_a

    taken_ary = sliced_ary[0].zip(*sliced_ary[1..])
    taken_ary.map!(&:compact).delete_if(&:empty?).map! { |x| insertion_sort(x) }

    ary = taken_ary[0].zip(*taken_ary[1..]).map(&:compact).flatten
    h = (h - 1) / 3
  end

  ary
end

これだけ仕様を調べてから書きました（参考）
我ながらいい感じのコードだと思います

クイックソート

def quick_sort(ary)
  return ary if ary.size == 1 || ary.all? { |x| x == ary[0] }

  middle = (ary.min + ary.max).fdiv(2)
  smaller, bigger = ary.partition { |x| x < middle }

  return quick_sort(smaller) + quick_sort(bigger)
end

初めて書いた再帰的プログラムです
短く纏められる再帰凄い（小並感）

おわり