Unexpected quicksort behaviour in R

Question

So I made a Monte Carlo Quicksort algorithm in R what uses sample function to determine the position of the new pivot at each iteration. My quicksort function looks like this:

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)
}

For testing purposes I initialize a vector with some random values at each execution of the script: arr=sample(1:30, size=5) This is what my function call looks like, along with the printing of the vector:

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

I tested the algorithm in Visual Studio (written in C++ of course) and I get the expected result each time. I'm guessing in R I'm doing something wrong about modifying the vector globally, but I can't figure it out. I'm hoping you have any ideas.

Answer 1

You are modifying arr globally; you seem to think that therefore the quicksort argument arr is modified. In addition your quicksort function should return arr. And the result of a quicksort call should be assigned to arr. arr will not be modified if you don't that. There is no need to use global assignment <<- for arr.

Change the quicksort function to this:

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
}

And now let's try again

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

Finally: please use <- for assignment. Avoid = which only assigns at toplevel.