# Time Complexity O(n^2)
# Space Complexity O(1)
# Neighbours change places until a pass makes
# no swaps: the largest element "bubbles up" to
# the end on every pass
bubble_sort <- function(lst) {
end <- length(lst)
while (end > 1) {
swapped <- FALSE
for (j in seq_len(end - 1)) {
if (lst[j + 1] < lst[j]) {
lst[c(j, j + 1)] <- lst[c(j + 1, j)]
swapped <- TRUE
}
}
if (!swapped) break
end <- end - 1
}
lst
}
items <- c(4, 1, 5, 3, 2)
sort_items <- bubble_sort(items)
# sort_items = 1 2 3 4 5
cat("items =", items, "\n")
cat("sort_items =", sort_items, "\n")
# *** simplified speed test ***
items <- 199:1
count <- 100
elapsed <- system.time(
for (i in seq_len(count)) {
bubble_sort(items)
})[["elapsed"]]
total_ms <- elapsed * 1000
cat("total_ms =", total_ms, "\n")