R Program to Implement Insertion Sort

1. Introduction

Insertion Sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, its straightforward nature makes it an excellent choice for small datasets. In this guide, we will detail how to implement the Insertion Sort algorithm in R.

2. Program Overview

The program will:

1. Define a function for the Insertion Sort algorithm.

2. Create a vector with a series of numbers.

3. Use the Insertion Sort function to sort the vector.

4. Display the sorted vector.

3. Code Program

# Define the Insertion Sort function
insertionSort <- function(vec) {
  n <- length(vec)

  # Traverse through 1 to length of the vector
  for (i in 2:n) {
    key <- vec[i]
    j <- i - 1

    # Move elements that are greater than the key
    # to one position ahead of their current position
    while (j >= 1 && vec[j] > key) {
      vec[j + 1] <- vec[j]
      j <- j - 1
    }
    vec[j + 1] <- key
  }

  # Return the sorted vector
  return(vec)
}

# Create a vector
numbers <- c(56, 12, 89, 45, 23, 24)

# Sort the vector using Insertion Sort
sorted_numbers <- insertionSort(numbers)

# Display the sorted vector
cat("Sorted vector using Insertion Sort:", sorted_numbers, "\n")

Output:

Sorted vector using Insertion Sort: 12 23 24 45 56 89

4. Step By Step Explanation

1. We begin by defining the insertionSort function. This function takes a vector and sorts it using the Insertion Sort method.

2. The length of the vector is determined using the length function.

3. Starting from the second element (indexed at 2), we regard it as a key.

4. For each key, we compare it with the previous elements. If the previous elements are larger than the key, we shift them to the right.

5. This continues until we reach an element smaller than the key or the start of the vector. The key is then placed in its correct position.

6. This process is repeated for every element in the vector, thus sorting the entire vector.

7. After the sorting is complete, the function returns the sorted vector.

8. We create a vector called "numbers" and sort it using the insertionSort function.

9. Finally, the sorted vector is printed using the cat function.

Note: Insertion Sort, while simple, tends to be efficient for smaller datasets or datasets that are nearly sorted. However, its performance drops significantly as the data size grows.