How to write insertion sort in R

Getting started with insertion sort

The insertion sort algorithm works by constructing a sorted vector one element at a time:

• First element: a vector with one element is already trivially sorted.
• Second element: if the second element is less than the first, swap them. We now have an increasing sorted vector of length two.
• Third element: perform any necessary swaps to move the third element into the correct position relative to the first to elements. We now have an increasing sorted vector of length three.

This process continues until the entire input vector is fully sorted.

For example, we want to sort the vector 4, 3, 2, 1 in increasing order using insertion sort. The algorithm will perform the following rearrangements of our input:

• Input: 4, 3, 2, 1
• Intermediary step: 3, 4, 2, 1 (first two elements sorted in increasing order)
• Intermediary step: 2, 3, 4, 1 (first three elements sorted in increasing order)
• Final step: 1, 2, 3, 4 (all four elements sorted in increasing order)

The insertion sort implementation in R

Let’s write an insertion sort function in R that arranges a numeric vector of two or more elements in increasing order:

insertion_sort <- function(x) {
  # The first loop goes through the elements of x to build a partially sorted vector
  # The first element is already trivially sorted, so we start the index at 2
  for (i in 2:length(x)) {
    # The second loop performs swaps to place the current element in its correct place
    for (j in i:2) {
      if (x[j - 1] > x[j]) {
        tmp <- x[j]
        x[j] <- x[j - 1]
        x[j - 1] <- tmp
      }
    }
  }
  # The sorted vector is returned
  return(x)
}

Testing our insertion sort R program

We can now test our insertion sort function on a few random input vectors:

for (i in 1:4) {
  x <- sample(1:10)
  cat("Input: ", x, "\n")
  cat("Output: ", insertion_sort(x), "\n")
}

## Input:  10 1 3 4 5 2 6 9 7 8 
## Output:  1 2 3 4 5 6 7 8 9 10 
## Input:  6 10 2 7 8 3 4 9 5 1 
## Output:  1 2 3 4 5 6 7 8 9 10 
## Input:  4 3 10 1 9 7 2 6 5 8 
## Output:  1 2 3 4 5 6 7 8 9 10 
## Input:  10 8 3 9 2 5 6 4 1 7 
## Output:  1 2 3 4 5 6 7 8 9 10

All output vectors are sorted in increasing order as expected.

We can also add two lines to our program that print the current state of the vector after each step:

insertion_sort <- function(x) {
  # The first loop goes through the elements of x to build a partially sorted vector
  # The first element is already trivially sorted, so we start the index at 2
  for (i in 2:length(x)) {
    # The second loop performs swaps to place the current element in its correct place
    for (j in i:2) {
      if (x[j - 1] > x[j]) {
        tmp <- x[j]
        x[j] <- x[j - 1]
        x[j - 1] <- tmp
      }
      cat("Swap performed:", x, "\n")
    }
    cat("First", i, "elements are sorted: ", x, "\n")
  }
  # The sorted vector is returned
  return(x)
}

This allows us to track the progress of insertion sort as it orders the input vector:

insertion_sort(c(4, 3, 2, 1))

## Swap performed: 3 4 2 1 
## First 2 elements are sorted:  3 4 2 1 
## Swap performed: 3 2 4 1 
## Swap performed: 2 3 4 1 
## First 3 elements are sorted:  2 3 4 1 
## Swap performed: 2 3 1 4 
## Swap performed: 2 1 3 4 
## Swap performed: 1 2 3 4 
## First 4 elements are sorted:  1 2 3 4

## [1] 1 2 3 4

For a full collection of R programming tutorials and exercises visit my website at codeRtime.org and the codeRtime YouTube channel.