Negin Zarbakhsh Negin Zarbakhsh - 11 days ago 12
R Question

insertion sort algorithm in R

I am new in programming and i am trying to learn about algorithms and implementing them in R. Here is my attempt at an insertion sort:

# insertion sort algorithm
inserionsort_function <- function(A){
for (j in 2:length(A)) {
key = A[j]
# insert A[j] into sorted sequence A[1,...,j-1]
i = j - 1
while (i > 0 & A[j] > key) {
A[(i + 1)] = A[i]
i = i - 1
}
A[(i + 1)] = key
}
}

inserionsort_function(c(5, 2, 4, 6, 1, 3))



my code run without any error but the output of my function is not true

Answer

There are at least 4 problems with your code, 1 minor and 3 major:

1) There is a typo in the name, you probably meant insertionsort_function (which is needlessly verbose -- why not just insertionsort?)

2) You aren't returning anything. If you want to return a sorted copy of the original array, have A by itself be the last line of the function. R returns the last expression in a function definition.

3) A[j] > key should be A[i] > key

4) & (which is for vectors) should be replaced by && (which is for logical conditions).

Making these changes yields:

insertionsort_function <- function(A){
  for (j in 2:length(A)) {
    key = A[j] 
    # insert A[j] into sorted sequence A[1,...,j-1] 
    i = j - 1 
    while (i > 0 && A[i] > key) {
      A[(i + 1)] = A[i]
      i = i - 1 
    }
    A[(i + 1)] = key
  }
  A
} 

For example,

> insertionsort_function(c(5, 2, 4, 6, 1, 3))
[1] 1 2 3 4 5 6

I am not convinced that R is a good language for learning the absolute basics of programming. If you do want to learn programming specifically in R, I would recommend a book which explicitly uses R to teach programming. For example, I found the book Hands-On Programming with R a good place to start. It is a quick read which teaches the fundamentals of programming in an R context.

Comments