Getting started

The bubble sort algorithm works by swapping neighboring entries of an input vector if they are not in the desired order. This process is repeated until no more swaps are necessary: the vector is already sorted.

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

• Input: 4, 3, 2, 1
  
• Intermediary step (first pass through the vector): 3, 4, 2, 1
  
• Intermediary step (first pass through the vector): 3, 2, 4, 1
  
• Intermediary step (first pass through the vector): 3, 2, 1, 4
  
• Intermediary step (second pass through the vector): 2, 3, 1, 4
  
• Intermediary step (second pass through the vector): 2, 1, 3, 4
  
• Final step (third pass through the vector): 1, 2, 3, 4

The bubble sort implementation

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

# Input: numeric vector of two or more elements
bubble_sort <- function(x) {
  swap_performed <- TRUE
  # Repeat the algorithm until no more swaps are performed
  while (swap_performed) {
    swap_performed <- FALSE
    # Check if any swaps are necessary
    for (i in 1:(length(x) - 1)) {
      if (x[i] > x[i + 1]) {
        # Swap elements that are not in increasing order
        tmp <- x[i]
        x[i] <- x[i + 1]
        x[i + 1] <- tmp
        # Now record that a swap was performed
        # This requests another pass through the while loop
        swap_performed <- TRUE
      }
    }
  }
  # Output: the vector sorted in increasing order
  return(x)
}

Testing our implementation

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

for (i in 1:4) {
  x <- sample(1:10)
  cat("Input: ", x, "\n")
  cat("Output: ", bubble_sort(x), "\n")
}
## Input:  1 5 6 8 2 10 9 3 4 7 
## Output:  1 2 3 4 5 6 7 8 9 10 
## Input:  9 7 2 8 3 4 5 10 6 1 
## Output:  1 2 3 4 5 6 7 8 9 10 
## Input:  1 10 6 8 5 7 2 9 4 3 
## Output:  1 2 3 4 5 6 7 8 9 10 
## Input:  9 5 7 2 6 4 1 3 10 8 
## 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 a line to our program that prints the current state of the vector after each swap:

# Input: numeric vector of two or more elements
bubble_sort <- function(x) {
  swap_performed <- TRUE
  # Repeat the algorithm until no more swaps are performed
  while (swap_performed) {
    swap_performed <- FALSE
    # Check if any swaps are necessary
    for (i in 1:(length(x) - 1)) {
      if (x[i] > x[i + 1]) {
        # Swap elements that are not in increasing order
        tmp <- x[i]
        x[i] <- x[i + 1]
        x[i + 1] <- tmp
        # Now record that a swap was performed
        # This requests another pass through the while loop
        swap_performed <- TRUE
        # Print the current state of our vector
        cat("Current state: ", x, "\n")
      }
    }
  }
  # Output: the vector sorted in increasing order
  return(x)
}

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

bubble_sort(c(1, 3, 5, 2, 4, 6))
## Current state:  1 3 2 5 4 6 
## Current state:  1 3 2 4 5 6 
## Current state:  1 2 3 4 5 6
## [1] 1 2 3 4 5 6