能否一起探讨下R中对两有序数组进行合并成一个有序数组的问题？

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

看一本R语言的书，其中有一个问题如下：
Write a program to merge two sorted vectors into a single sorted vector.
Do not use the sort(x) function, and try to make your program as efficient
as possible. That is, try to minimise the number of operations required to
merge the vectors.
能否一起探讨一下有效的算法，我先抛砖引玉，思想来自网络的帖子：

1. a <- -10:10
   
2. b <- 2:8
   
3. checkSort <- function(x) {
   
4. result = TRUE
   
5. for (i in 1:(length(x) - 1)) {
   
6. for (j in (i + 1):length(x)) {
   
7. if (x[j - 1] > x[j]){
   
8. result <- FALSE
   
9. break
   
10. }
    
11. }
    
12. }
    
13. return(result)
    
14. }
    
15. 
    
16. mergesort <- function(a, b) {
    
17. if (checkSort(a) & checkSort(b)){
    
18. a.length <- length(a)
    
19. b.length <- length(b)
    
20. n <- a.length + b.length
    
21. result.vec <- rep(0, n)
    
22. i <- 1
    
23. j <- 1
    
24. k <- 1
    
25. while(i <= a.length & j <= b.length){
    
26. if(a[i] <= b[j]) {
    
27. result.vec[k] <- a[i]
    
28. i <- i +1
    
29. k <- k + 1
    
30. } else {
    
31. result.vec[k] <- b[j]
    
32. j <- j + 1
    
33. k <- k + 1
    
34. }
    
35. }
    
36. while(i <= a.length) {
    
37. result.vec[k] <- a[i]
    
38. i <- i +1
    
39. k <- k + 1
    
40. }
    
41. while(j <= b.length) {
    
42. result.vec[k] <- b[j]
    
43. j <- j + 1
    
44. k <- k + 1
    
45. }
    
46. return(result.vec)
    
47. } else {
    
48. cat("please input two sorted vectors")
    
49. }
    
50. 
    
51. }
    
52. mergesort(a, b)

复制代码

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：一起探讨 行合并 Operations EFFICIENT operation function possible required number single

mergesort算法，这个就是

想写一个看起来像R的排序方法，可是问题也来了。当从数组中删除最后一个元素时，R将个这个数组赋值为长度为1，值为0的数组。这个怎么处理比较好？下面是我写的代码

1. #########################
   
2. ## R style merger sort ##
   
3. #########################
   
4. 
   
5. m_sort <- function(iter_list){
   
6.     stopifnot(iter_list$len>0)
   
7.     xx <- iter_list$x;yy <- iter_list$y;kk <-iter_list$k
   
8.     print(paste("xx=",length(xx),sep=""),env=.GlobalEnv)
   
9.     print(paste("yy=",length(yy),sep=""),env=.GlobalEnv)
   
10.     indeks <- NA
    
11.     if(min(xx)<=min(yy) && length(xx)>0){
    
12.         vec_in_globe[kk+1] <<- min(xx)
    
13.         indeks <- which.min(xx)
    
14.         iter_list$x <- xx[-indeks]
    
15.     }
    
16.     if(min(yy)<min(xx) && length(yy)>0){
    
17.         vec_in_globe[kk+1] <<- min(yy)
    
18.         indeks <- which.min(yy)
    
19.         iter_list$y <- yy[-indeks]
    
20.     }
    
21.     iter_list$k <- kk+1
    
22.     iter_list$len <- iter_list$len-1
    
23.     m_sort(iter_list)
    
24. }
    
25. 
    
26. a <- 1:10;b <- 2:8;k <- 1;len <- length(a)+length(b)
    
27. vec_in_globe <- numeric(len)
    
28. iter_list <- list(x=a[!is.na(a)],y=b[!is.na(b)],k=k,len=len)
    
29. m_sort(iter_list)

复制代码

输出的结果如下：

1. > a <- 1:10;b <- 2:8;k <- 1;len <- length(a)+length(b)
   
2. > vec_in_globe <- numeric(len)
   
3. > iter_list <- list(x=a[!is.na(a)],y=b[!is.na(b)],k=k,len=len)
   
4. > m_sort(iter_list)
   
5. [1] "xx=10"
   
6. [1] "yy=7"
   
7. [1] "xx=9"
   
8. [1] "yy=7"
   
9. [1] "xx=8"
   
10. [1] "yy=7"
    
11. [1] "xx=8"
    
12. [1] "yy=6"
    
13. [1] "xx=7"
    
14. [1] "yy=6"
    
15. [1] "xx=7"
    
16. [1] "yy=5"
    
17. [1] "xx=6"
    
18. [1] "yy=5"
    
19. [1] "xx=6"
    
20. [1] "yy=4"
    
21. [1] "xx=5"
    
22. [1] "yy=4"
    
23. [1] "xx=5"
    
24. [1] "yy=3"
    
25. [1] "xx=4"
    
26. [1] "yy=3"
    
27. [1] "xx=4"
    
28. [1] "yy=2"
    
29. [1] "xx=3"
    
30. [1] "yy=2"
    
31. [1] "xx=3"
    
32. [1] "yy=1"
    
33. [1] "xx=2"
    
34. [1] "yy=1"
    
35. [1] "xx=2"
    
36. [1] "yy=0"
    
37. [1] "xx=1"
    
38. [1] "yy=0"
    
39. Error: iter_list$len > 0 is not TRUE
    
40. In addition: Warning messages:
    
41. 1: In min(yy) : no non-missing arguments to min; returning Inf
    
42. 2: In min(yy) : no non-missing arguments to min; returning Inf
    
43. 3: In min(yy) : no non-missing arguments to min; returning Inf
    
44. 4: In min(yy) : no non-missing arguments to min; returning Inf
    
45. > vec_in_globe
    
46. [1]  0  1  2  2  3  3  4  4  5  5  6  6  7  7  8  8  9 10

复制代码

期望的输出是

1. [1]  1  1  2  2  3  3  4  4  5  5  6  6  7  7  8  8  9 10

复制代码

这是对空数组赋值0造成的

nuomin 发表于 2014-2-6 08:37
想写一个看起来像R的排序方法，可是问题也来了。当从数组中删除最后一个元素时，R将个这个数组赋值为长度为 ...

您好，您在程序里面令k<-0就会出现正确结果，另外看到您程序里有一些警告，可以修改如下就不出现警告了。

1. #########################
   
2. ## R style merger sort ##
   
3. #########################
   
4. 
   
5. m_sort <- function(iter_list){
   
6.   stopifnot(iter_list$len>0)
   
7.   xx <- iter_list$x;yy <- iter_list$y;kk <-iter_list$k
   
8.   indeks <- NA
   
9.   if (length(xx)>0 && length(yy)>0){
   
10.     if(min(xx)<=min(yy)){
    
11.       print(paste("xx=",length(xx),sep=""),env=.GlobalEnv)
    
12.       vec_in_globe[kk+1] <<- min(xx)
    
13.       indeks <- which.min(xx)
    
14.       iter_list$x <- xx[-indeks]
    
15.     }
    
16.     if(min(yy)<min(xx)){
    
17.       print(paste("yy=",length(yy),sep=""),env=.GlobalEnv)
    
18.       vec_in_globe[kk+1] <<- min(yy)
    
19.       indeks <- which.min(yy)
    
20.       iter_list$y <- yy[-indeks]
    
21.     }
    
22.    
    
23.   }else if(length(xx)>0) {
    
24.     print(paste("xx=",length(xx),sep=""),env=.GlobalEnv)
    
25.     vec_in_globe[kk+1] <<- min(xx)
    
26.     indeks <- which.min(xx)
    
27.     iter_list$x <- xx[-indeks]
    
28.   } else if (length(yy)>0) {
    
29.     print(paste("yy=",length(yy),sep=""),env=.GlobalEnv)
    
30.     vec_in_globe[kk+1] <<- min(yy)
    
31.     indeks <- which.min(yy)
    
32.     iter_list$y <- yy[-indeks]
    
33.   }
    
34.   
    
35.   iter_list$k <- kk+1
    
36.   iter_list$len <- iter_list$len-1
    
37.   m_sort(iter_list)
    
38. }
    
39. 
    
40. a <- 1:10;
    
41. b <- 2:8;
    
42. k <- 0;
    
43. len <- length(a)+length(b)
    
44. vec_in_globe <- numeric(len)
    
45. iter_list <- list(x=a[!is.na(a)],y=b[!is.na(b)],k=k,len=len)
    
46. m_sort(iter_list)
    
47. vec_in_globe

复制代码

结果是：

1. > m_sort(iter_list)
   
2. [1] "xx=10"
   
3. [1] "xx=9"
   
4. [1] "yy=7"
   
5. [1] "xx=8"
   
6. [1] "yy=6"
   
7. [1] "xx=7"
   
8. [1] "yy=5"
   
9. [1] "xx=6"
   
10. [1] "yy=4"
    
11. [1] "xx=5"
    
12. [1] "yy=3"
    
13. [1] "xx=4"
    
14. [1] "yy=2"
    
15. [1] "xx=3"
    
16. [1] "yy=1"
    
17. [1] "xx=2"
    
18. [1] "xx=1"
    
19. Error: iter_list$len > 0 is not TRUE
    
20. > vec_in_globe
    
21. [1] 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 10

复制代码

另外想请问一下，您的这行命令里

1. print(paste("yy=",length(yy),sep=""),env=.GlobalEnv)

复制代码

env=.GlobalEnv有什么样的作用，谢谢！

kaifengedu 发表于 2014-2-6 11:14
您好，您在程序里面令k

在最顶端的环境输出