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.
As @dickoa noted, use print. However, if you're using the GUI, printed output is by default buffered until the function returns. You can force the printout to occur immediately with flush.console.
qs <- function(vec) {
# print input vector
print(vec); flush.console()
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
}
Sample run:
> z <- sample(10)
> qs(z)
[1] 2 6 1 4 8 5 9 7 3 10
[1] 1
[1] 6 4 8 5 9 7 3 10
[1] 4 5 3
[1] 3
[1] 5
[1] 8 9 7 10
[1] 7
[1] 9 10
integer(0)
[1] 10
[1] 1 2 3 4 5 6 7 8 9 10
You can do it by passing the whole vector at each function call, together with "start" and "end" parameters to describe which slice of the vector you're currently sorting. Here's my first attempt at doing this. Maybe you can write a more elegant version?
qs<-function(vec,start=1,finish=length(vec)) {
if (finish>start) {
pivot<-vec[start]
N<-length(vec)
window<-((1:N)>=start) & ((1:N)<=finish)
low_part<-vec[(vec<pivot) & window]
mid_part<-vec[(vec==pivot) & window]
high_part<-vec[(vec>pivot) & window]
if (start>1) cat(vec[1:(start-1)],"| ")
cat(low_part,">>>",mid_part,"<<<",high_part)
if (finish<N) cat(" |",vec[(finish+1):N])
cat("\n")
vec[window]<-c(low_part,mid_part,high_part)
if (length(low_part)>0) {
low_top<-start+length(low_part)-1
vec[start:low_top]<-qs(vec,start,low_top)[start:low_top]
}
if (length(high_part)>0) {
high_bottom<-finish-length(high_part)+1
vec[high_bottom:finish]<-qs(vec,high_bottom,finish)[high_bottom:finish]
}
}
return(vec)
}
qs(sample(1:30,replace=TRUE))
