R中意外的快速排序行爲

Question

所以我在R中做了一個蒙特卡洛快速排序算法，它使用函數來確定每次迭代中新的關鍵點的位置。 我的快速排序函數如下所示：arr=sample(1:30, size=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) 
    quickSort(arr, left, j) 
    if(i < right) 
    quickSort(arr, i, right) 
} 

出於測試目的，我在劇本的每一個執行初始化一些隨機值向量向量：

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

我在Visual Studio中測試了算法（當然是用C++寫的），每次都得到預期的結果。我在R猜測我在全局修改矢量時做錯了什麼，但我無法弄清楚。我希望你有任何想法。

Answer 1

您正在修改全球範圍內的arr;你似乎認爲，因此修改了快速排序參數arr。另外你的quicksort函數應該返回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 

最後：請用<-進行分配。避免只在頂層分配的=。

Answer 2

我認爲你的問題是使用<<-。首先，即使arr不是您傳遞給quickSort的變量的名稱，也要更新父環境中名爲arr的變量。但是，在之內，函數arr仍然被具有相同名稱的局部變量遮蔽 - 例如，您對quickSort的遞歸調用將按照原始順序傳遞矢量，而不是以更新順序傳遞矢量。

試試這個。請注意，它返回更新後的向量，而不是嘗試在父環境中更新它，但如果要更新原始變量，當然可以始終將其稱爲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 
}