# Time Complexity from O(n log(n)) to O(n^2)
# Space Complexity O(log(n))
# elements less than the middle one go left,
# greater go right, then each part is sorted
# the same way
quick_sort <- function(data) {
lst <- data
sort_part <- function(first, last) {
if (first >= last) return()
i <- first
j <- last
x <- lst[(first + last) %/% 2]
while (i <= j) {
while (lst[i] < x) i <- i + 1
while (lst[j] > x) j <- j - 1
if (i <= j) {
lst[c(i, j)] <<- lst[c(j, i)]
i <- i + 1
j <- j - 1
}
}
sort_part(first, j)
sort_part(i, last)
}
sort_part(1, length(lst))
lst
}
items <- c(4, 1, 5, 3, 2)
sort_items <- quick_sort(items)
# sort_items = 1 2 3 4 5
cat("items =", items, "\n")
cat("sort_items =", sort_items, "\n")
# *** simplified speed test ***
items <- 1:199
items[c(6, 7)] <- items[c(7, 6)]
count <- 1000
elapsed <- system.time(
for (i in seq_len(count)) {
quick_sort(items)
})[["elapsed"]]
total_ms <- elapsed * 1000
cat("total_ms =", total_ms, "\n")