【アルゴリズムの勉強】Rubyで二分探索（バイナリサーチ）を書いてみる
アルゴリズムの勉強としてRubyで二分探索（バイナリサーチ）を実装する。
二分探索とは
ソート済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。
大小関係を用いるため、未ソートのリストや大小関係の定義されない要素を含むリストには二分探索を用いることはできない。
n個のデータがある場合、時間計算量はOlog2nである（O記法）。
n個のデータの中央の値を見ることで、1回の操作でn/2個程度（奇数の場合は(n-1)/2個、偶数の場合はn/2個または(n/2)-1個）の要素を無視することができる。
Rubyで実装
arr = [2, 4, 6, 9, 10, 12, 15, 20, 25, 60] number_of_elements = arr.count def binary_search(arr, number_of_elements, target) left = 0 right = number_of_elements - 1 while left <= right center = (left + right) / 2 if arr[center] == target return center elsif arr[center] < target left = center + 1 else right = center - 1 end end return -1 end target = 20 result = binary_search(arr, number_of_elements, target) if result == -1 puts "値が#{target}の要素は配列内に存在しません" else puts "要素の値が#{target}のインデックス => #{result}" end
【アルゴリズムの勉強】Rubyで番兵法を用いた線形探索を書いてみる
アルゴリズムの勉強としてRubyで番兵法を用いた線形探索を実装する。
番兵法とは
データの終了を示すために配置される特殊なデータを指す。この用語は、微妙に異なる以下の2つの意味で使われる。
・実データには出現しない、データの終了を表すための専用の値
・入力データを処理するループの終了条件が複数ある場合に、条件判定の数を削減するために置くダミーのデータ
Rubyで実装
arr = [4, 20, 6, 10, 2, 15, 60, 9, 25, 12] number_of_elements = arr.count def linear_search_with_sentinel_method(arr, number_of_elements, target) index = 0 arr[number_of_elements] = target loop do break if arr[index] == target index += 1 end if index == number_of_elements return -1 else return index end end target = 10 result = linear_search_with_sentinel_method(arr, number_of_elements, target) if result == -1 puts "値が#{target}の要素は配列内に存在しません" else puts "要素の値が#{target}のインデックス => #{result}" end
【アルゴリズムの勉強】Rubyで線形探索を書いてみる
線形探索とは
線形探索（せんけいたんさく、英: linear search, sequential search）は、検索のアルゴリズムの一つ。 リストや配列に入ったデータに対する検索を行うにあたって、 先頭から順に比較を行い、それが見つかれば終了する。
{\displaystyle n} n個のデータから {\displaystyle m} m個のデータを検索する場合、 時間計算量は {\displaystyle O(nm)} O(nm)、空間計算量は {\displaystyle O(1)} O(1)必要となる。
Rubyで実装
arr = [4, 20, 6, 10, 2, 15, 60, 9, 25, 12] number_of_elements = arr.count def linear_search(arr, number_of_elements, target) index = 0 loop do if index == number_of_elements return -1 elsif arr[index] == target return index end index += 1 end end target = 9 result = linear_search(arr, number_of_elements, target) if result == -1 puts "値が#{target}の要素は配列内に存在しません" else puts "要素の値が#{target}のインデックス => #{result}" end
【アルゴリズムの勉強】Rubyで分布数え上げソート（カウンティングソート、度数ソート）を書いてみる
アルゴリズムの勉強としてRubyで分布数え上げソート（カウンティングソート、度数ソートとも呼ばれる）を実装する。
分布数え上げソートとは
分布数え上げソートはソート対象のデータをキーにして、キーの出現回数とその累積度数分布を計算して利用することで整列を行うアルゴリズムです。 バケットソートと同じくキーとなるデータがとりうる値の範囲をあらかじめ知っている必要があります。バケットソートとの違いはキーの重複に対応したアルゴリズムであるということです。
Rubyで実装
arr = [4, 20, 6, 10, 2, 15, 60, 9, 25, 12, 9] number_of_elements = arr.count max = arr.max def counting_sort(arr, number_of_elements, max) counting_arr = Array.new(max + 1, 0) answer = [] for i in 0..(number_of_elements - 1) counting_arr[arr[i]] += 1 end for i in 1..max counting_arr[i] += counting_arr[i - 1] end (number_of_elements - 1).downto(0) {|i| key = counting_arr[arr[i]] - 1 answer[key] = arr[i] counting_arr[arr[i]] += -1 } return answer end sorted_arr = counting_sort(arr, number_of_elements, max) p sorted_arr # => [2, 4, 6, 9, 9, 10, 12, 15, 20, 25, 60]
参考文献、参考リンク
- 明解 Javaによるアルゴリズムとデータ構造
- 分布数え上げソート : アルゴリズム
【アルゴリズムの勉強】Rubyでヒープソートを書いてみる
ヒープソートとは
ヒープソート (heap sort) とはリストの並べ替えを二分ヒープ木を用いて行うソートのアルゴリズムである[2]（ヒープ領域とは無関係であることに注意する）。
アルゴリズムは、以下のように2つの段階から構成される。
未整列のリストから要素を取り出し、順にヒープに追加する。すべての要素を追加するまで繰り返し。
ルート（最大値または最小値)を取り出し、整列済みリストに追加する。すべての要素を取り出すまで繰り返し。
計算量は O {\displaystyle (n\log n)} (n\log n) となる[2]。安定ソートではない[2]。
Rubyで実装
arr = [4, 20, 6, 10, 2, 15, 60, 9, 25, 12] number_of_elements = arr.count def make_heap(arr, parent, end_element) temp = arr[parent] child = 0 while parent < (end_element + 1) / 2 left_child = (parent * 2) + 1 right_child = left_child + 1 if right_child <= end_element && arr[right_child] > arr[left_child] child = right_child else child = left_child end if temp >= arr[child] break end arr[parent] = arr[child] parent = child end arr[parent] = temp end def heap_sort(arr, number_of_elements) center = (number_of_elements - 1) / 2 while center >= 0 make_heap(arr, center, number_of_elements - 1) center += -1 end end_element = number_of_elements - 1 while end_element > 0 arr[0], arr[end_element] = arr[end_element], arr[0] make_heap(arr, 0, end_element - 1) end_element += -1 end end heap_sort(arr, number_of_elements) p arr # => [2, 4, 6, 9, 10, 12, 15, 20, 25, 60]
【アルゴリズムの勉強】Rubyでマージソートを書いてみる
マージソートとは
マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの分割統治法による。大きい列を多数の列に分割し、そのそれぞれをマージする作業は並列化できる。
n個のデータを含む配列をソートする場合、最悪計算量O(n log n)である。分割と統合の実装にもよるが、一般に安定なソートを実装できる。インプレースなソートも提案されているが、通常O(n)の外部記憶を必要とする[1]。
（ナイーブな）クイックソートと比べると、最悪計算量は少ない[1]。ランダムなデータでは通常、クイックソートのほうが速い。
Rubyで実装
arr = [4, 20, 6, 10, 2, 15, 60, 9, 25, 12] number_of_elements = arr.count buffer = [] def merge_sort(arr, left, right, buffer) if left < right center = (left + right) / 2 first_r = 0 first_l = 0 right_cursor = left left_cursor = left merge_sort(arr, left, center, buffer) merge_sort(arr, center + 1, right, buffer) while right_cursor <= center buffer[first_r] = arr[right_cursor] first_r += 1 right_cursor += 1 end while right_cursor <= right && first_l < first_r if buffer[first_l] <= arr[right_cursor] arr[left_cursor] = buffer[first_l] left_cursor += 1 first_l += 1 else arr[left_cursor] = arr[right_cursor] left_cursor += 1 right_cursor += 1 end end while first_l < first_r arr[left_cursor] = buffer[first_l] left_cursor += 1 first_l += 1 end end return arr end sorted_arr = merge_sort(arr, 0, number_of_elements - 1, buffer) p sorted_arr # => [2, 4, 6, 9, 10, 12, 15, 20, 25, 60]
【アルゴリズムの勉強】Rubyでクイックソートを書いてみる
アルゴリズムの勉強としてRubyでクイックソートを実装する。
クイックソートとは
クイックソート (quicksort) は、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。
n個のデータをソートする際の最良計算量および平均計算量はO {\displaystyle (n\log n)} (n\log n)である。他のソート法と比べて、一般的に最も高速だといわれているが対象のデータの並びやデータの数によっては必ずしも速いわけではなく、最悪の計算量はO {\displaystyle (n^{2})} (n^{2})である。また数々の変種がある。 安定ソートではない。
Rubyで実装
arr = [4, 20, 6, 10, 15, 2, 60, 9, 25, 12] number_of_elements = arr.count def quick_sort(arr, left_end, right_end) left_point = left_end right_point = right_end pivot = arr[(left_point + right_point) / 2] while left_point <= right_point while arr[left_point] < pivot left_point += 1 end while arr[right_point] > pivot right_point += -1 end if (left_point <= right_point) arr[left_point], arr[right_point] = arr[right_point], arr[left_point] left_point += 1 right_point += -1 end end quick_sort(arr, left_end, right_point) if left_end < right_point quick_sort(arr, left_point, right_end) if left_point < right_end end quick_sort(arr, 0, number_of_elements - 1) p arr # => [2, 4, 6, 9, 10, 12, 15, 20, 25, 60]
