【アルゴリズムの勉強】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]