# How to write bubble sort in R

**R programming tutorials and exercises for data science and mathematics**, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)

Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

**Topics covered:** number operations, vector operations, sorting algorithms

## 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

**leave a comment**for the author, please follow the link and comment on their blog:

**R programming tutorials and exercises for data science and mathematics**.

R-bloggers.com offers

**daily e-mail updates**about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.

Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.