了解 Ruby 类："undefined method `<' for true:TrueClass"

Question

我正在关注Coursera上的一个类，并试图用Ruby实现快速排序算法。我对OOP的语言和概念很陌生。

我创建了两个函数：一个是quickSort函数，它调用分区例程（根据数组的第一个元素pivot将数组拆分为两个子数组）。

最终，我会把这两个方法放在一个类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

感谢

Answer 1

left_idx < j < right_idx

你不能这样做。

left_idx<j首先解析为"True"

然后表达式变为真<right_idx和<是无效的运算符。。

将表达式更改为if left_idx<j&amp；j<right_idx

Answer 2

您不能这样做：

left_idx < j < right_idx and left_idx < i < right_idx

你需要建立条件：

((j > left_idx) && (j < left_idx)) && (etc)

Answer 3

问题出在这行：

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"。因此它尝试调用<在"true"类上，但它不存在，从而导致您得到的错误。

Answer 4

问题是这一行：

(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

这可能还可以做得更好。请注意，这还没有到位的快速排序，但你的似乎也没有到位。