【アルゴリズムの勉強】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]
【アルゴリズムの勉強】Rubyでシェルソートを書いてみる
シェルソートとは
シェルソート（改良挿入ソート、英語: Shellsort, Shell sort, Shell's method）は、in-placeな比較ソートのアルゴリズムの一種である。シェルソートは、交換によるソート（バブルソート）あるいは挿入によるソート（挿入ソート）の一般化と見なすことができる[2]。ソートの方法は、まず、間隔の離れた要素の組に対してソートを行い、だんだんと比較する要素間の間隔を小さくしながらソートを繰り返す、というものである。離れた場所の要素からソートを始めることで、単純に近くの要素を比較する場合よりも速く、要素を所定の位置に移動させることができる。ただし、安定ソートではない。ドナルド・シェル（Donald L. Shell）が、1959年に、シェルソートの最初のバージョンを公開した[3][4] 。シェルソートの実行時間は、比較時に選ぶ間隔によって大きく異なる。多くの実用的な方法が提案されているが、正確な時間計算量を求める方法は、未解決問題である。
Rubyで実装
arr = [4, 20, 6, 10, 15, 2, 60, 9, 25, 12] number_of_elements = arr.count def shell_sort(arr, number_of_elements) h = 1 # 効率を上げるため、121, 40, 13, 4, 1となるような間隔を作る while h < (number_of_elements / 9) h = h * 3 + 1 end while h > 0 for i in h..(number_of_elements - 1) j = i - h target = arr[i] while j >= 0 && arr[j] > target arr[j + h] = arr[j] j += -h end arr[j + h] = target end h = h / 3 end return arr end sorted_arr = shell_sort(arr, number_of_elements) p sorted_arr # => [2, 4, 6, 9, 10, 12, 15, 20, 25, 60]
【アルゴリズムの勉強】Rubyで選択ソートを書いてみる
選択ソートとは
選択ソート（英: selection sort）は、ソートのアルゴリズムの一つ。配列された要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えをおこなうこと。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。内部ソート。後述するように、安定ソートではない。
このアルゴリズムを改良したソート法として、ヒープソートが挙げられる。
Rubyで実装
arr = [4, 20, 6, 10, 2, 15, 60, 9, 25, 12] number_of_elements = arr.count def selection_sort(arr, number_of_elements) (number_of_elements - 1).times{|i| min = i for j in (i + 1)..(number_of_elements - 1) if arr[j] < arr[min] min = j; end end arr[i], arr[min] = arr[min], arr[i] } return arr end sorted_arr = selection_sort(arr, number_of_elements) p sorted_arr # => [2, 4, 6, 9, 10, 12, 15, 20, 25, 60]
