Лабораторная работа по замеру времени сортировки разными алгоритмами

Скрипт, написанный на языке 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))$