insertionsort.R

#' ---
#' title: "Inserion Sort in R"
#' author: "Rahul Goswami"
#' ---

#' This function implements the insertion sort algorithm
#' The basic idea of insertion sort is to maintain a sorted sublist in the lower positions of the list, and then pick
#' the element from the upper part and put it in the correct position.
#' It's average case time complexity is O(n^2)



insertion.sort <- function(vec){
    # Iterate over the vector
    for(i in 2:length(vec)){
        # Initialize the index of the element to be inserted
        j <- i
        # While the index of the element to be inserted is greater than 0
        while(j > 1 && vec[j] < vec[j-1]){
            # Swap the elements
            temp <- vec[j]
            vec[j] <- vec[j-1]
            vec[j-1] <- temp
            # Decrement the index of the element to be inserted
            j <- j - 1
        }
    }
    vec
}


#' ### Example
vector <- c(7,6,5,1,0,9,5,5)
insertion.sort(vector)