shellsort.R

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

#' Shell sort is a sorting algorithm , usually in bubble sort we swap the adjacent elements if they are in wrong order.
#' Shell sort is an improvement over bubble sort where it swap the elemnts of the array in a gap.
#' The idea is to start with a large gap and then reduce the gap.
#' The basic idea of shell 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.  

#' Lets create a function that implements the shell sort algorithm.  

shell.sort <- function(vec){
    # Iterate over the vector
    for(i in 1:length(vec)){
        # Initialize the gap
        gap <- floor(length(vec)/2)
        # Iterate over the unsorted list
        while(gap > 0){
            # Iterate over the sublist
            for(j in (gap+1):length(vec)){
                # If the element at j is smaller than the element at j-gap
                if(vec[j] < vec[j-gap]){
                    # Swap the elements
                    temp <- vec[j]
                    vec[j] <- vec[j-gap]
                    vec[j-gap] <- temp
                }
            }
            # Decrement the gap
            gap <- floor(gap/2)
        }
    }
    vec
}


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