-1

我正在关注 Coursera 上的课程，并且正在尝试在 Ruby 中实现快速排序算法。我对 OOP 的语言和概念非常陌生。

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

最终，我会将这两个方法放在一个类 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始终为真或假，然后您尝试与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 回答