1

C ++での挿入ソートのアルゴリズムは次のとおりです（チュートリアルから）。

void insertionSort(int arr[], int length) {
      int i, j, tmp;
      for (i = 1; i < length; i++) {
            j = i;
            while (j > 0 && arr[j - 1] > arr[j]) {
                  tmp = arr[j];
                  arr[j] = arr[j - 1];
                  arr[j - 1] = tmp;
                  j--;
            }
      }
}

これが私がRubyでやっていることです

a = [12, 1, 18, -3, -2, 66, 31]
puts a

def insertion_sort(source)
    source.to_enum.with_index(1).each do |item, i|
        j = i
        while((j>0) && (source[j-1] > source[j]))
            source[j], source[j-1] = source[j-1], source[j]
            j -= 1  
        end
    end
end

insertion_sort(a)
puts a

のエラーをスローしますcomparison of Fixnum with nil failed (ArgumentError)。おそらくオーバーフローが原因です。

私は何を間違えましたか？

4

2 に答える 2

2

あなたが持っているC++バージョンでは(i = 1; i < length; i++)。つまり、最後のラウンドは実行されませんi = length。それは配列から外れるでしょう。

ではruby、インデックスのオフセットを1最後のラウンドであるに設定したため、はになりますi = length。したがって、source[length]から外れているsourceので、を返しますnil。

1 > nil  # source[j-1] > source[j] when j = length
# ArgumentError: comparison of Fixnum with nil failed
于 2012-10-29T04:46:48.713 に答える
1

@oldergodはすでにあなたの質問に答えていますが、問題にいくつかの修正を追加したいと思います。

ここにアルゴリズムgemから取られたコードのサンプルがあります

def insertion_sort(container)
  return container if container.size < 2
  (1..container.size-1).each do |i|
    value = container[i]
    j = i-1
    while j >= 0 and container[j] > value do
      container[j+1] = container[j]
      j = j-1
    end
    container[j+1] = value
  end
  container
end

1ここでは、コンテナの2番目のインデックスである数値をcontainer.size - 1最後のインデックスまで繰り返します。

于 2012-10-29T07:54:30.820 に答える