Неожиданное поведение быстрой сортировки в R

Question

Итак, я сделал алгоритм Монте-Карло Quicksort в R, который использует 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 вызов должен быть назначен 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 в родительской среде, даже если 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
}