予期しないクイックソート動作がR

Question

であるため、RでMonte Carlo Quicksortアルゴリズムを作成しました。sample関数は、各繰り返しで新しいピボットの位置を決定します。 私のクイックソート機能は、次のようになります。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をグローバルに変更しています。したがって、quicksort引数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は、同じ名前のローカル変数によってまだシャドーされています。たとえば、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 
}