R 中意外的快速排序行为

Question

所以我在 R 中创建了一个 Monte Carlo 快速排序算法，该算法使用 sample 函数来确定每次迭代时新枢轴的位置。我的快速排序函数如下所示：

quickSort=function(arr, left, right) {
  i = left
  j = right
  pivot = arr[sample(left:right, size=1)]
  while (i <= j) {
    while (arr[i] < pivot)
      i=i+1
    while (arr[j] > pivot)
      j=j-1
    if (i <= j) {
      tmp = arr[i]
      arr[i] <<- arr[j]
      arr[j] <<- tmp
      i=i+1
      j=j-1
    }
  }
  if (left < j)
    quickSort(arr, left, j)
  if(i < right)
    quickSort(arr, i, right)
}

出于测试目的，我在每次执行脚本时用一些随机值初始化一个向量：arr=sample(1:30, size=5) 这是我的函数调用的样子，连同矢量的打印：

quickSort(arr, 1, 5)
print(arr)

我在 Visual Studio 中测试了算法（当然是用 C++ 编写的），每次都能得到预期的结果。我猜在 R 中我在全局修改向量方面做错了，但我想不通。我希望你有任何想法。

Answer 1

我认为您的问题出在 <<- 的使用上。首先，您正在更新父环境 中名为 arr 的变量，即使 arr 不是您传递给 quickSort 的变量的名称。而且，在函数 arr 仍然被具有相同名称的局部变量覆盖——所以例如你对 quickSort 的递归调用正在按原始顺序传递向量，而不是向量更新后的顺序。

试试这个。请注意，它 returns 是更新后的向量，而不是尝试在父环境中更新它，当然，如果你愿意，你总是可以像 arr <- quickSort(arr, 1, 5) 这样称呼它更新原始变量。

quickSort=function(arr, left, right) {
    i = left
    j = right
    pivot = arr[sample(left:right, size=1)]
    while (i <= j) {
        while (arr[i] < pivot)
            i=i+1
        while (arr[j] > pivot)
            j=j-1
        if (i <= j) {
            tmp = arr[i]
            arr[i] <- arr[j]
            arr[j] <- tmp
            i=i+1
            j=j-1
        }
    }
    if (left < j)
        arr <- quickSort(arr, left, j)
    if(i < right)
        arr <- quickSort(arr, i, right)
    arr
}

Answer 2

您正在全局修改 arr；您似乎认为因此修改了快速排序参数 arr 。此外，您的 quicksort 函数应该 return arr。 quicksort 调用的结果应分配给 arr。如果您不这样做，arr 将不会被修改。 arr.

不需要使用全局赋值 <<-

将quicksort函数改成这样：

quickSort=function(arr, left, right) {
  i = left
  j = right
  pivot = arr[sample(left:right, size=1)]
  while (i <= j) {
    while (arr[i] < pivot)
      i=i+1
    while (arr[j] > pivot)
      j=j-1
    if (i <= j) {
      tmp = arr[i]
      arr[i] <- arr[j]
      arr[j] <- tmp
      i=i+1
      j=j-1
    }
  }
  if (left < j)
    arr <- quickSort(arr, left, j)
  if(i < right)
    arr <- quickSort(arr, i, right)
  arr
}

现在让我们再试一次

arr=sample(1:30, size=5) 
arr
#    [1] 27 28  8 15 18
quickSort(arr, 1, 5)
#    [1]  8 15 18 27 28

最后：请用<-赋值。避免只在顶层分配的 =。

R 中意外的快速排序行为

Unexpected quicksort behaviour in R

r

quicksort

montecarlo