Rubyでのマージソートの調査

以下は、Rubyで記述されたマージソートアルゴリズムです。

class MergeSort
  def sort(numbers)

    num_elements = numbers.length
    if num_elements <= 1
      return numbers
    end

    half_of_elements = (num_elements / 2).round

    left  = numbers.take(half_of_elements)
    right = numbers.drop(half_of_elements)

    sorted_left = sort(left)
    sorted_right = sort(right)

    merge(sorted_left, sorted_right)
  end

  def merge(left_array, right_array)
    if right_array.empty?
      return left_array
    end

    if left_array.empty?
      return right_array
    end

    smallest_number = if left_array.first <= right_array.first
      left_array.shift
    else
      right_array.shift
    end

    recursive = merge(left_array, right_array)

    [smallest_number].concat(recursive)
  end
end

ここで何が起こっているのかを見ていきましょう。まず、sortに焦点を当てます 上部のメソッド。

  def sort(numbers)

    num_elements = numbers.length
    if num_elements <= 1
      return numbers
    end

    half_of_elements = (num_elements / 2).round

    left  = numbers.take(half_of_elements)
    right = numbers.drop(half_of_elements)

    sorted_left = sort(left)
    sorted_right = sort(right)

    merge(sorted_left, sorted_right)
  end

コードのこの部分の目標は、それぞれに1つのアイテムだけが残るまで、指定された数値を半分に分割することです。実際の動作を確認するには、最後の行（merge（sorted_left、sorted_right））をコメントアウトし、代わりにsorted_leftを出力します。 およびsorted_right 。サンプル配列を渡してプログラムを実行すると、ターミナルに次のように表示されます。

merge_sort = MergeSort.new
puts merge_sort.sort([38, 27, 43, 3, 9, 82, 10])

ruby ruby-merge-sort.rb

27
43
38

3
9
82
10

すごい！私たちのコードは最初の配列を取り、それを半分に分割しました。 mergeを見てみましょう 次のコードの一部。

  def merge(left_array, right_array)
    if right_array.empty?
      return left_array
    end

    if left_array.empty?
      return right_array
    end

    smallest_number = if left_array.first <= right_array.first
      left_array.shift
    else
      right_array.shift
    end

    recursive = merge(left_array, right_array)

    [smallest_number].concat(recursive)
  end

まず、いずれかのサブ配列が空かどうかを確認します。もしそうなら、私たちは単にもう一方を返すことができます。それ以外の場合は、両方のサブ配列が空でない場合、各配列の最初の要素の値を比較してから、比較した値をシフトして、無限ループが作成されないようにします。次に、2つの配列を最終的に接続して適切にソートできるようになるまで、元の配列で再帰を利用します（これについては後ほど詳しく説明します）。