CODEWITHSUNDEEP
rquicksortmontecarlo
Peter
Peter

Reputation: 337

Unexpected quicksort behaviour in R

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.

Upvotes: 2

Views: 60

Answers (2)

Bhas
Bhas

Reputation: 1834

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.

Upvotes: 1

Tim Goodman
Tim Goodman

Reputation: 23976

I think your problem is with the use of <<-. First of all, you're updating the variable named arr in the parent environment even if arr wasn't the name of the variable you passed in to quickSort. But also, within the function arr is still shadowed by the local variable with the same name -- so for instance your recursive calls to quickSort are being passed the vector in the original order, not the vector in the updated order.

Try this instead. Note that it returns the updated vector, rather than trying to update it in the parent environment, but of course you can always call it like arr <- quickSort(arr, 1, 5) if you want to update the original variable.

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
}

Upvotes: 1

Related Questions