Скрипт, написанный на языке R, который автоматически тестирует и замеряет, как быстро работают популярные алгоритмы сортировки:
-
Bubblesort
$~ O(n^2)$ -
Selection sort
$~ O(n^2)$ -
Insert sort
$~ O(n^2)$ -
Merge sort
$~ O(n*log(n))$
и строит график времени выполнения
Проект очень простой, состоит из 4 файлов:
├── utils.R # Вспомогательные функции
├── sorts.R # алгоритмы сортировки
├── unit_tests.R # Юнит тесты
├── plots.R # Построение графика
└── main.R # Точка входа
Исполните файл main.R
Генерировались случайные списки заданной длинны и замерялось время (timestamp) выполнения программы
Поскольку результаты выполнения функций кэшируются, то списки для сортировки генерируются случайным образом:
get_random_list <- function(n = 10) {
return(sample(1:100, n, replace = TRUE))
}
Для удобного замера времени использовались декораторы
timer <- function(f) {
wrapper <- function(...) {
op <- options(digits.secs = 15)
start <- proc.time()
res <- f(...)
end <- proc.time()
return((end - start)["elapsed"])
}
return(wrapper)
}
И далее, создавались функции-таймеры для конкретных алгоритмов сортировки
sa_timer <- timer(sorting_algorithm)
sa_timer(get_random_list(n))) # Выведет время выполнения алгоритма, для случайного списка длины n
Далее, подставлялись нужные значения из промежутка, сохраняясь в отдельный список времени выполнения
обе функции находятся в модуле utils
Получились следующие результаты:
Примерная функциональная зависимость:
- Для Insert sort:
$y(n) = \frac{n^2}{4 * 10^7} \in O(n^2)$ - Для Merge sort:
$y(n) = \frac{n*log(n)}{6 * 10^5} \in O(n * log(n))$