如何制作可能为空的序列？

Question

我最近尝试将 some pseudocode 改编为就地快速排序，引用如下：

function quicksort(array)
    if length(array) > 1
        pivot := select any element of array
        left := first index of array
        right := last index of array
        while left ≤ right
            while array[left] < pivot
                left := left + 1
            while array[right] > pivot
                right := right - 1
            if left ≤ right
                swap array[left] with array[right]
                left := left + 1
                right := right - 1
        quicksort(array from first index to right)
        quicksort(array from left to last index)

在此之后，我写了这段代码：

quicksort<-function(array)
{
  len<-length(array)
  if(len>1)
  {
    left<-1
    right<-len
    pivot<-array[(left+right)%/%2]
    while(left<=right)
    {
      while(array[left]<pivot){left<-left+1}
      while(array[right]<pivot){right<-right-1}
      if(left<=right)
      {
        array[c(left,right)]<-array[c(right,left)]
        left<-left+1
        right<-right-1
      }
    }
    array<-quicksort(array[1:right])#Bug here
    array<-quicksort(array[left:len])
  }
  array
}

如果您运行此代码将多个整数作为输入，您会发现它最终会尝试对 NA 列表进行排序。我怀疑问题是伪代码希望 array from first index to right - 我的 1:right - 在 right 为零时被读取为空序列。众所周知，R 实际上读作 1:0 作为序列 0 1.

是否有任何函数可以实现我想要的行为？我可以用 if 语句来做到这一点，但 R 通常对序列足够好，我忍不住认为会有更好的方法。我尝试使用 seq，但如果您尝试使用 seq(from=1,to=0,by=1).

之类的内容，它会抛出错误

Answer 1

代码有两个问题：

其中一个不等号被翻转了。
数组赋值需要修改为仅更改元素的子集而不是替换（和收缩）整个数组。

这是更正后的代码

quicksort <- function(array) {
  len <- length(array)
  if(len > 1) {
    left <- 1
    right <- len
    pivot <- array[(left+right)%/%2]
    while(left <= right)
    {
      while(array[left] < pivot){ 
        left <- left + 1
      }
      while(array[right] > pivot) { # Changed "<" to ">"
        right <- right - 1
      }
      if(left <= right) {
        array[c(left, right)] <- array[c(right, left)]
        left <- left + 1
        right <- right - 1
      }
    }
    
    # Modified the following two lines to only set a subset of array
    array[1:right] <- quicksort(array[1:right])
    array[left:len] <- quicksort(array[left:len])
  }
  array
}


quicksort(c(2, 6, 3, 1, 4, 5))
#> [1] 1 2 3 4 5 6

如何制作可能为空的序列？

How to make sequences that may be empty?

sorting

r

list

quicksort

sequence