-1

Coursera のクラスをフォローしており、Ruby でクイックソート アルゴリズムを実装しようとしています。私は言語と OOP の概念に非常に慣れていません。

2 つの関数を作成しました。1 つはパーティション ルーチンを呼び出す quickSort 関数です (配列の最初の要素であるピボットに従って、配列を 2 つのサブ配列に分割します)。

最終的には、これら 2 つのメソッドをクラス Array の下に配置しますが、今のところ、これで問題ないと判断しました。

これを配列 (a = [5, 4, 3, 2, 1]) で実行しようとしましたが、次のエラーが発生しました。

A2.rb:16:in `partition': undefined method `<' for true:TrueClass (NoMethodError)
    from A2.rb:15:in `each'
    from A2.rb:15:in `partition'
    from A2.rb:33:in `quickSort'

これが私のコードです：

    def partition(array, left_idx, right_idx)
      num_comp = array.length - 1
      p = array[left_idx]
      i = left_idx + 1
      j = left_idx + 1
      puts "#{left_idx}, #{right_idx}, #{array[j]} #{j}"
      puts "pivot = #{p}"
      for j in (left_idx + 1..right_idx)
        if (left_idx < j < right_idx and left_idx < i < right_idx)
          if (array[j] > p)
            j = j + 1
          else 
            array[i], array[j] = array[j], array[i]
            i = i + 1
            j = j + 1
          end
        end
      end
      #swap pivot and rightmost value in subarray that contains < p
      array[1], array[i] = array[i], array[1]
      pivot_idx = i
      return array, num_comp, pivot_idx
    end

    def quickSort(array, start_idx, end_idx)
      array_n, num_comp, pivot_idx = partition(array, start_idx, end_idx)
      left_array = array_n[start_idx..pivot_idx - 1]
      right_array = array_n[pivot_idx + 1..end_idx]
      if (left_array.length > 1) 
        array_n = quickSort(array_n, start_idx, pivot_idx - 1)
      end
      if (right_array.length > 1)
        array_n = quickSort(array_n, pivot_idx + 1, end_idx)
      end
      return array
    end

    #a = Array.new()
    a = [5, 4, 3, 2, 1]
    quickSort(a, 0, 4)
    print "Array"
    puts a

ありがとう

4

4 に答える 4

4 
left_idx < j < right_idx

これはできません。

left_idx < j は最初に「True」に解決されます

そして、式は true < right_idx になり、 < は無効な演算子です..

式を if left_idx < j && j < right_idx に変更します

于 2013-02-14T21:32:26.490 に答える
2

これを行うことはできません:

left_idx < j < right_idx and left_idx < i < right_idx

条件を構築する必要があります：

((j > left_idx) && (j < left_idx)) && (etc)
于 2013-02-14T21:32:01.657 に答える
0

問題は次の行にあります。

if (left_idx < j < right_idx and left_idx < i < right_idx)

これは有効な数学ですが、無効な Ruby (そして他のほとんどのプログラミング言語でも無効です)。代わりに必要なのは次のとおりです。

if (left_idx < j and j < right_idx and left_idx < i and i < right_idx)

何が起こっているかというと、Ruby は "<" をメソッドとして解釈します。したがって、元の行は次のようになります。

if ((left_idx.<(j)).<(right_idx)) and ((left_idx.<(i)).<(right_idx))

あなたの場合、 (left_idx.<(j)) の結果は「true」です。そのため、「真の」クラスで < を呼び出そうとしますが、存在しないため、エラーが発生します。

于 2013-02-14T21:32:32.610 に答える
0

問題は次の行です。

(left_idx < j < right_idx and left_idx < i < right_idx)

left < middle < rightは、数学では普通に書くものかもしれませんが、Ruby では<特別なことではなく、ただのメソッドです。具体的には、ブール値を返すメソッドです。の結果left_idx < jは常に true または false であり、right_idxその値と比較しようとしています。明らかに、それは意味がありません。

その行を次のように書くことができます

left_idx < j && j < right_idx #...

また

(left_idx..right_idx).include? j && (left_idx..right_idx).include? i

また

([i,j].all? {|v| (left_idx..right_idx).include? v})

クイックソートを書くためのやや慣用的な方法は次のようになります

def quicksort(arr)
   pivot, *rest = arr
   left,right = rest.partition{|v| v<pivot}.map{|a| if !a.empty? then quicksort(a) else a end}
   left.push(pivot) + right
end

これはおそらくまだうまくいく可能性があります。これはインプレースのクイックソートではありませんが、あなたのものもそうではなかったことに注意してください。

于 2013-02-14T21:48:00.147 に答える