快速排序在R：我如何打印中间步骤？ [英] Quicksort in R: How do I print the intermediate steps?

问题描述

我承认我的算法知识还不是很不错的。我写了使用基本的递归在研发一个快速排序的功能。我的问题是，我该如何修改这个算法也显示每次迭代之间的中间载体。我知道有一个聪明的方法来与跟踪做到这一点，你的支点，但我在努力找出自己。

  QS＆LT;  - 功能（VEC）{

  如果（长度（VEC）→1）{

    枢轴＆所述;  -  vec的[1]

    低＆LT;  -  QS（VEC [VEC＆LT;透视]）
    中期和LT;  -  VEC [VEC ==支点]
    高＆LT;  -  QS（VEC [VEC＆GT;透视]）

    C（低，中，高）


  }

  其他VEC

}
 

解决方案

PS：我不知道，但你的实现可能是根据非常低效的R如何实现与逻辑数组下标

您不能没有在当前状态下花费太多的记忆在里面（即使用递归）做到这一点。

如果你想保持递归： 这是深度优先的方法。初始化数组的数组。第一个索引的深度和相应的阵列会给你在该深度的状态。跟踪深度（即通过深度作为一个参数），并追加子阵列到相应的深度。

code：

  printableList =空数组的数组
QS＆LT;  - 功能（VEC，深度）{
printableList [深度] = printableList [深度] + VEC

  如果（长度（VEC）→1）{
    枢轴＆所述;  -  vec的[1]
    低＆LT;  -  QS（VEC [VEC＆LT;透视]，深度+ 1）
    中期和LT;  -  VEC [VEC ==支点]
    高＆LT;  -  QS（VEC [VEC＆GT;透视]，深度+ 1）

    C（低，中，高）
  }
  其他VEC
}
 

或者 您还可以实现整个事情作为一个广度优先的方法。你将必须实现整个事情与队列。在这里，因为你处理的子问题层逐层你只需要打印出来。

I admit my knowledge of algorithms isn't very good. I wrote a quicksort function in R using basic recursion. My question is, how do I modify this algorithm to also display the intermediate vectors between each iteration. I know there is a clever way to do it with tracking where your pivot is but I'm struggling to figure it out myself.

qs <- function(vec) {

  if(length(vec) > 1) {

    pivot <- vec[1]

    low <- qs(vec[vec < pivot])
    mid <- vec[vec == pivot]
    high <- qs(vec[vec > pivot])

    c(low, mid, high)


  }

  else vec

}

解决方案

PS: I am not sure, but your implementation might be very inefficient depending on how R implements subscripting with a logical array.

You cannot do it without spending too much memory in it in the current state (i.e. using recursion).

If you want to keep recursion: This is depth first approach. Initialize an array of arrays. The first index is the depth and the corresponding array would give you the state at that depth. Keep track of depth (i.e. pass depth as a parameter) and append the subarray to the corresponding depth.

Code:

printableList = Array of empty arrays 
qs <- function(vec, depth) {
printableList[depth] = printableList[depth] + vec

  if(length(vec) > 1) {
    pivot <- vec[1]
    low <- qs(vec[vec < pivot], depth+1)
    mid <- vec[vec == pivot]
    high <- qs(vec[vec > pivot], depth+1)

    c(low, mid, high)
  }
  else vec
}

Alternatively: You can also implement the whole thing as a breadth first approach. You will have to implement the whole thing with a queue. Here, since you process the sub-problems layer-by-layer you just have to print them.

这篇关于快速排序在R：我如何打印中间步骤？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！