递归冒泡排序ruby

Question

我正在尝试在Ruby中构建一个递归气泡排序方法。它可以通过一次，但之后它会不断返回。看来我的if array == swapped_array正在被触发，但我不明白我的array变量在哪里被重新定义。

def bubble_sort(array, swapped = true)
  return array if swapped == false
  i = 0
  if swapped == true
    swapped_array = comparator(array)
  end
  if array == swapped_array
    swapped = false
    bubble_sort(array, swapped)
  else bubble_sort(swapped_array)
  end
end
def comparator(array, i = 0)
  return array if i == array.length - 1
  if array[i] > array[i+1]
    array[i], array[i+1] = array[i+1], array[i]
  end
  i += 1
  comparator(array, i)
end

Answer 1

swapped_array = comparator(array)

…取comparator的返回值并赋值给swapped_array。但是comparator(最终)返回原始参数array，它与调用者中定义的array相同。所以

array == swapped_array

总是为真。

如果你想比较两个不同的数组，你可以在数组上调用.dup。这会创建一个与原始对象具有相同值的新对象。

Answer 2

这是因为在comparator中，您正在交换原始数组中的元素。无论您对它做什么，bubble_sort中的array和swapped_array都引用相同的数组实例，因此将始终相同。要解决这个问题，在定义的顶部添加一行:

def comparator(array, i = 0)
  array = array.dup
  ...
end