Brute Force: Selection Sort or Bubble Sort

To begin, I first installed and loaded all the necessary packages and dependencies to RStudio Desktop.

Load packages:

library(rmarkdown)
library(knitr)
library(ggplot2)
library(gganimate)
library(gifski)
library(dplyr)
library(plotly)

Suppose we have a vector called my_number that contains all the digits (including duplicates) of my cellphone number.

## Selection Sort Algorithm


my_number <- c(0, 9, 9, 3, 3, 8, 1, 3, 3, 0, 7)


selection_sort <- function(my_number) {
  n <- length(my_number)  

  for (i in 1:(n-1)) {    #[1]
    min_index <- i        #[2]
    for (j in (i+1):n) {  
      if (my_number[j] < my_number[min_index]) {
        min_index <- j    #[3]
      }
    }
      
    if (min_index != i) { 
      temp <- my_number[i]
      my_number[i] <- my_number[min_index]
      my_number[min_index] <- temp   #[4]
    }
      
  }
  return(my_number)
}


my_number <- selection_sort(my_number) #[5]

my_number

##  [1] 0 0 1 3 3 3 3 7 8 9 9

Explanation:

[1] Outer loop always iterates n-1 times. [2] Set first unsorted element’s index as index_minimum. [3] Finds the smallest element and stores its index at index_minimum, if and only if the current element is less than the element associated with index_minimum.
[4] Swap minimum element with first unsorted element’s position. [5] Call the function then assign to my_number.

## Selection Sort Visualization Function

selection_sort_viz <- function(my_number) {
  n <- length(my_number)
  steps <- list()
  
  # Add initial state
  steps[[1]] <- data.frame(
    index = 1:n,
    value = my_number,
    step = sprintf("Step %03d", 1)
  )
  
  step_num <- 2
  
  for (i in 1:(n - 1)) {
    min_index <- i
    for (j in (i + 1):n) {
      if (my_number[j] < my_number[min_index]) {
        min_index <- j
      }
    }
    
    if (min_index != i) {
      # Swap values
      temp <- my_number[i]
      my_number[i] <- my_number[min_index]
      my_number[min_index] <- temp
      
      # Save current state after the swap
      steps[[length(steps) + 1]] <- data.frame(
        index = 1:n,
        value = my_number,
        step = sprintf("Step %03d", step_num)
      )
      step_num <- step_num + 1
    }
  }
  
  return(dplyr::bind_rows(steps))
}

my_number <- c(0, 9, 9, 3, 3, 8, 1, 3, 3, 0, 7)
sort_steps <- selection_sort_viz(my_number)

In this visualization, notice that index 1 and index 10 are seemingly empty. That is because my number has two zeroes placed at the first element and tenth element. It is worth noting that the y-axis begins at zero.

library(ggplot2)
library(gganimate)
library(dplyr)

ggplot(sort_steps, aes(x = factor(index), y = value, fill = factor(index))) +
  geom_col(show.legend = FALSE) +
  labs(
    title = "Selection Sort Visualization",
    subtitle = "{closest_state}",
    x = "Index",
    y = "Value"
  ) +
  gganimate::transition_states(step, transition_length = 2, state_length = 3) +
  gganimate::ease_aes("linear")

## Bubble Sort Algorithm

my_number <- c(0, 9, 9, 3, 3, 8, 1, 3, 3, 0, 7)

bubble_sort <- function(my_number) {
  n <- length(my_number)
  
  for (i in 1:(n-1)) {
    for (j in 1:(n-i)) {
      if (my_number[j] > my_number[j+1]) {
        temp <- my_number[j+1]
        my_number[j+1] <- my_number[j]
        my_number[j] <- temp
      } 
    }
  }
  return (my_number)
}  

my_number <- bubble_sort(my_number)

my_number

##  [1] 0 0 1 3 3 3 3 7 8 9 9

Visualization of Bubble Sort

## Bubble Sort Visualization

my_number <- c(0, 9, 9, 3, 3, 8, 1, 3, 3, 0, 7)

bubble_sort_viz <- function(my_number) {
  n <- length(my_number)
  steps <- list()
  
  steps[[1]] <- data.frame(
    index = 1:n,
    value = my_number,
    step = sprintf("Step %03d", 1)
  )
  
  step_num <- 2
  
  for (i in 1:(n-1)) {
    for (j in 1:(n-i)) {
      if (my_number[j] > my_number[j+1]) {
        temp <- my_number[j+1]
        my_number[j+1] <- my_number[j]
        my_number[j] <- temp
       
      
        steps[[length(steps) + 1]] <- data.frame(  #[1]
        index = 1:n,
        value = my_number,
        step = sprintf("Step %03d", step_num)
      )
      step_num <- step_num + 1
    }
  }
}

  return(dplyr::bind_rows(steps)) #[2]
}  

[1] Capture each state of the bubble sort after each swap. [2] Bind all captured states.

my_number <- c(0, 9, 9, 3, 3, 8, 1, 3, 3, 0, 7)
sort_steps <- bubble_sort_viz(my_number)

ggplot(sort_steps, aes(x = factor(index), y = value, fill = factor(index))) +
  geom_col(show.legend = FALSE) +
  labs(
    title = "Bubble Sort Visualization",
    subtitle = "{closest_state}",
    x = "Index",
    y = "Value"
  ) +
  gganimate::transition_states(step, transition_length = 2, state_length = 3) +
  gganimate::ease_aes("linear")

My Observations:

• Selection sort and Bubble Sort are different.

• Bubble sort compares and swaps two elements at once if and only if a criteria was satisfied. To visualize these two pointers, I imagine two hands that compares each banana in a supermarket to find the largest one. Personally, it is much faster compared to selection sort.

• Selection sort will only swap two elements once it reaches the last index. Its strength, I think, would be its ability to find the largest or smallest element in just one iteration. Though I do not recommended using it in searching algorithms.

Thank you for taking the time to read my work. I spent a lot of time debugging. Finally, I could now sleep.