-1

I would need some help to understand this type of code and the action that happens here. For instance, we take a vector x defined by the integer (8,6,5,4,2,1,9).

The first step of this function would be to check if the condition is given, that the length of this vector is higher than 1. For x, the condition is given. The next step is to highlight the position of the smallest value in this vector, this is 6. But I dont understand what actually happens in the next steps and why it has to combine it as a vector?

selsort <- function(x) {
  if(length(x) > 1) {
    mini <- which.min(x)
    c(x[mini], selsort(x[-mini])) #selsort() somewhere in here -> recursion
  } else x   
}
tompave
  • 11,952
  • 7
  • 37
  • 63
user3514864
  • 29
  • 1
  • 3

2 Answers2

2

In recursion, there are 2 key cases:

Base case - input produces a result directly

Recursive case - input causes the program to call itself again

In your function, the base case is when the length of x is not greater than 1. When this happens, we just return x. When we reach the base case, we will not be running the function any more times, all it will do is back track through all of the previous recursive cases to finish executing those selsort() calls.

The recursive case is when the length is greater than 1. For this, we combine the smallest value in our vector with the result of selsort() without that smallest value. This will continue until we reach the base case. So, we find the smallest value, remove it from the list, and then repeat with all of the values from the previous run except the one we selected. Once we reach the base case of there only being 1 element left (the largest one), we have no more minimum finding to do, so we just return the last element.

This is called selection sort, because we are specifically selecting 1 element each time (the smallest element). With large data, this is inefficient, but it is a natural way to think about sorting.

There are more efficient sorting algorithms. One nice one that is easy to understand is merge sort: Merge Sort in R

Community
  • 1
  • 1
Morris Greenberg
  • 343
  • 2
  • 8
1

It puts the smallest number at the first position of the vector, removes this entry from the vector and recursively repeats this until the entire vector entries are sorted from smallest to largest number.

Example

In the first step

x <- x1 <- c(8,6,5,4,2,1,9)

the position of the smallest number in the vector is identified by selsort() with the which.min() function. This number is put at the first position. At the same time, this element is removed from the vector. Therefore in the next step one has

x2 <- c(8,6,5,4,2,9)
c(1,selsort(x2))

Now the algorithm searches for the smallest number in x2, which is 2, puts that one on the front and removes it from the vector, leading to:

x3 <- c(8,6,5,4,9)
c(1,c(2,selsort(x3)))

This is repeated until the length of the vector is equal to one. Then there is nothing left to sort and the last number is returned, which is the largest element of the initial vector.

The assignments x1, x2, x3... are mentioned here only to illustrate the sequence of operation of the code. This is done implicitly in the recursive function which uses only one vector x and reduces it by one entry at each iteration.

Hope this helps.

Community
  • 1
  • 1
RHertel
  • 23,412
  • 5
  • 38
  • 64