在 r 中插入排序，错误"missing value where TRUE/FALSE needed"

Question

我想在r:中构建插入排序算法

1. 给定向量x，让初始未排序向量u等于x，
   并且初始排序向量s是长度为0的向量
2. 删除u的第一个元素并将其插入s中，这样s仍然是排序的
3. 如果u不为空，则返回步骤2

这是我的代码：

x <- round(runif(1000,1,100)
u <- x
s <- vector(mode="numeric", length=0

for(i in 1:length(u)){
number <-u[i]
u <- u[-i]
for(j in 1:length(s)){
if(length(s) == 0){
s <- c(s,number)
break
}else{
if(s[j]>=number){
s <- append(s,number,j-1)
break
}
}
if(s[length(s)]<number){
s <- c(s,number)
}
}
}

首先，当长度u=500时，它会给我一个错误：

Error in if (s[j] >= number) { : missing value where TRUE/FALSE needed

接下来，它的排序不正确(例如，它可能比原始向量u中的1多，或者例如，比原始向量u中的2少)

所以我有两个问题：

1) 我们如何在THIS代码中解决这个问题？

2) 你能建议另一个比我的代码更有效的代码吗？

第页。S当然，代码应该没有排序命令。非常感谢

Answer 1

你的第一个问题很容易解决：当你从向量u中提取一个数字时，你真正要做的只是从样本中随机抽取一个数字，而不需要替换。所以总是取第一个值。

# Change the current to this:
number <-u[1]
u <- u[-1]

---

对于您的第二个问题：多么有趣的练习！我的尝试是实现维基百科中的选择排序伪代码(你可以这样做)，但要蒙上眼睛：我不能看x的"袋子"，只能看到我刚画的项目——我发现这更像你想要的。

我该如何解决这个问题？简单：我从x中提取一个值。称之为我的control变量。然后，对于每一次绘图，如果小于(或等于)控制，我将新值放入一堆small中。否则，我将其放入large堆中。当我分配了所有的值后，我会对每一堆再次执行此算法。我继续，直到我的桩都达到1号。这一点的实施情况如下。

mysort <- function(x){
if(length(x) <= 1){
return(x)       ## If nothing to sort, return itself
}
control <- x[1]
small <- c()
big <- c()
for(test in x[-1]){
if(test <= control){
small <- c(small,test)  ## Less than control in small
}
if(test > control){
big <- c(big,test)      ## Bigger than control in big
}
}
## Sort the new piles with the same procedure recursively.
small <- mysort(small)          
big <- mysort(big)
## Return the improved order
c(small,control,big)
}
mysort(c(2,1,1,2,2,2,3,3,-3,-Inf,Inf,0,pi))
# [1]      -Inf -3.000000  0.000000  1.000000  1.000000  2.000000  2.000000  2.000000
# [9]  2.000000  3.000000  3.000000  3.141593       Inf

---

如果我们将您的实现(没有多余的while-循环)封装在函数yoursort中，我们可以将速度与microbenchmark包进行比较。

library(microbenchmark)
a <- rnorm(1e3)
microbenchmark(b <- mysort(a),times = 10)
# Unit: milliseconds
#           expr      min      lq     mean   median       uq      max neval
# b <- mysort(a) 37.76747 39.2302 41.96171 40.99288 43.07412 47.85377    10
microbenchmark(c <- yoursort(a),times = 10)
# Unit: milliseconds
#             expr      min       lq     mean   median       uq      max neval
# c <- yoursort(a) 786.4544 808.2312 861.8072 840.7868 879.4946 1059.913    10
microbenchmark(sort(a),times = 10)
# Unit: microseconds
#    expr     min      lq     mean   median      uq     max neval
# sort(a) 192.763 194.384 242.7633 201.1335 263.497 390.386    10

两者都与已经实现的sort函数不匹配。

当然，他们真的做了正确的排序吗？

any(b != sort(a)) ## Are there any elements that do not match?
# [1] FALSE
any(c != sort(a))
# [1] FALSE