report.txt

---------------------------------Links-------------------------------------------
Repo link: https://github.com/schukark/sorting_benchmark
Google colab python file link: https://colab.research.google.com/drive/1ZMJVu-Ldgs7eZPA6302UqqY6u30HZd1p?usp=sharing
---------------------------------------------------------------------------------
---------------------------------File structure----------------------------------
sorting_benchmark/
├─ benchmark_results/
├─ src/
│  ├─ Data_structures/
│  │  ├─ skip_list.cpp
│  │  ├─ heap.cpp
│  ├─ bubble_sorter.cpp
│  ├─ g_quick_sorter.cpp
│  ├─ heap_sorter.cpp
│  ├─ insertion_bin_sorter.cpp
│  ├─ insertion_sorter.cpp
│  ├─ merge_sorter.cpp
│  ├─ quick_sorter.cpp
│  ├─ skip_list_sorter.cpp
│  ├─ sorter.cpp
│  ├─ sorters_list.hpp
├─ .gitignore
├─ benchmark.cpp
├─ collect_data.cpp
├─ README.md
├─ report.txt
├─ sorting_benchmark.ipynb
---------------------------------------------------------------------------------
---------------------------------Description-------------------------------------
Каждый файл .cpp в папке Data_structures представляет реализацию вспомогательной 
структуры данных

Каждый другой .cpp файл в папке src содержит реализацию конкретного сортировщика

Файл benchmark.cpp содержит реализацию тестирующей системы

Файл collect_data.cpp содержит вызов всех видов сортировок из условия задания

Папка benchmark_results содержит текстовые файлы, в которых содержатся
результаты тестирования сортировок в табличном или псевдо-табличном виде
---------------------------------------------------------------------------------
---------------------------------head.cpp----------------------------------------
#pragma once

#ifndef HEAP_CPP

#include <cstddef>

inline size_t left_child(size_t child) {
    return 2 * child + 1;
}

inline size_t right_child(size_t child) {
    return 2 * child + 2;
}

inline size_t parent(size_t child) {
    return (child - 1) / 2;
}

template<class T>
class Heap {
public:
    Heap(std::vector<T>& arr): arr(arr) {
        heapify();
    }

    /// @brief Sorts the vector from heap, destroying the heap in the process
    /// @return sorted vector
    std::vector<T> get_sorted() {
        std::vector<T> ans(arr.size());
        int n = arr.size();
        for (int i = 0; i < n; i++) {
            ans[i] = extract_min();
        }

        return ans;
    }

private:
    /// @brief Sift the element down in the heap
    /// @param index element to be sifted
    void sift_down(size_t index) {
        while (index < arr.size()) {
            size_t left = left_child(index);
            size_t right = right_child(index);

            size_t min_ind = index;
            if (right < arr.size() && arr[right] < arr[min_ind]) {
                min_ind = right;
            }
            if (left < arr.size() && arr[left] < arr[min_ind]) {
                min_ind = left;
            }

            if (min_ind != index) {
                std::swap(arr[index], arr[min_ind]);
                index = min_ind;
            }
            else {
                break;
            }
        }
    }

    /// @brief Makes heap from vector
    void heapify() {
        for (int i = arr.size() / 2 - 1; i >= 0; i--) {
            sift_down(i);
        }
    }

    /// @brief Find minimum and delete it from heap
    /// @return the minimum
    T extract_min () {
        T min_value = arr.front();
        std::swap(arr.front(), arr.back());
        arr.pop_back();
        sift_down(0);

        return min_value;
    }

    std::vector<T> arr;
};

#endif
---------------------------------------------------------------------------------
---------------------------------skip_list.cpp-----------------------------------
#pragma once

#ifndef SKIP_LIST_CPP
#include <vector>
#include <random>

std::random_device rd;
std::mt19937 gen(rd());
std::uniform_real_distribution<double> coin_flip(0.0, 1.0);

template<class T>
class SkipListNode {
public:
    SkipListNode(const T& value, int level, bool empty_node=false): value(value), empty_node(empty_node) {
        if (!empty_node) {
            for (int i = 0; i < level; i++) {
                T def_value;
                forward.emplace_back(new SkipListNode(def_value, 0, true));
            }
        }
    }
    
    std::vector<SkipListNode*> forward;
    T value;
    bool empty_node;
};

template<class T>
class SkipList {
public:
    SkipList(): probablity_of_promotion(0.5), kMaxLevel(16) {
        T default_value;
        head = new SkipListNode<T>(default_value, kMaxLevel);
        null_node = new SkipListNode<T>(default_value, kMaxLevel, true);

        for (size_t i = 0; i < head->forward.size(); ++i) {
            head->forward[i] = null_node;
        }
    }

    ~SkipList() {
        delete head;
        delete null_node;
    }

    //! HELPERS

    /// @brief Get random level according to skip list rule
    /// @return random level
    int get_random_level() {
        int level = 1;
        while (coin_flip(gen) <= probablity_of_promotion && level < kMaxLevel) {
            level++;
        }

        return level;
    }

    /// @brief Counts number of nodes connected to this node
    /// @param node
    /// @return Number of nodes
    int count_nodes(const SkipListNode<T>* node) {
        return node->forward.size();
    }

    //! Modifying functions
    
    /// @brief Inserts a given value in the skip-list
    /// @param value 
    void insert(const T& value) {
        std::vector<SkipListNode<T>*> needs_updates(head->forward);
        int cur_max_level = count_nodes(head);
        SkipListNode<T>* current = head;

        for (int i = cur_max_level - 1; i >= 0; i--) {
            while (!current->forward[i]->empty_node && current->forward[i]->value < value) {
                current = current->forward[i];
            }

            needs_updates[i] = current;
        }

        int new_node_level = get_random_level();
        current = new SkipListNode<T>(value, new_node_level);

        for (int i = 0; i < new_node_level; ++i) {
            current->forward[i] = needs_updates[i]->forward[i];
            needs_updates[i]->forward[i] = current;
        }
    }

    /// @brief returns the head of the skip_list
    /// @return 
    SkipListNode<T>* get_head() {
        return head;
    }

private:
    SkipListNode<T>* head;
    SkipListNode<T>* null_node;

    double probablity_of_promotion;
    const int kMaxLevel;
};


/// @brief Generate a skip-list from a vector
/// @tparam T vector elements' data type
/// @param data vector of elements
/// @return constructed skip list
template<class T>
SkipList<T> list_from_vector(std::vector<T>& data) {
    SkipList<T> result;

    for (const auto& it : data) {
        result.insert(it);
    }

    return result;
}

/// @brief Makes a sorted vector from stored skip-list
/// @tparam T vector elemtns' data type
/// @param list skip-list to convert to vector
/// @return sorted vector
template<class T>
std::vector<T> vector_from_skip_list(SkipList<T>& list) {
    std::vector<T> answer;
    SkipListNode<T>* current = list.get_head()->forward[0];

    while (!current->empty_node) {
        answer.push_back(current->value);
        current = current->forward[0];
    }

    return answer;
}

#endif
---------------------------------------------------------------------------------
---------------------------------bubble_sorter.cpp-------------------------------
#pragma once

#ifndef BUBBLE_SORTER_CPP

#include "Sorter.cpp"
#include <vector>

template<class T>
class BubbleSorter: public Sorter<T> {
public:
    BubbleSorter(): Sorter<T>(1e4, "Bubble sort") {}

    void sort(std::vector<T>& data, int l, int r) override {
        for (int i = 0; i < data.size(); i++) {
            for (int j = i + 1; j < data.size(); j++) {
                if (data[i] > data[j]) {
                    std::swap(data[i], data[j]);
                }
            }
        }
    }

private:

};

#endif
---------------------------------------------------------------------------------
---------------------------------g_quick_sorter.cpp------------------------------
#pragma once

#ifndef G_QUICK_SORTER_CPP

#include "Sorter.cpp"
#include <vector>
#include <random>
#include <algorithm>
#include <assert.h>

template<class T>
class GQuickSorter : public Sorter<T> {
public:
    GQuickSorter() : Sorter<T>(1e6, "Guaranteed quick sort"), gen(rd()) {}

    void sort(std::vector<T>& data, int l, int r) override {
        if (l >= r) {
            return;
        }

        int part = partition(data, l, r);

        sort(data, l, part - 1);
        sort(data, part + 1, r);
    }

private:
    /// @brief Function needed by quick sort to partition an array based on the pivoting element
    /// @param data full vector to be sorted
    /// @param left left boundary of the "to be sorted" subarray
    /// @param right right boundary
    /// @return the index of the pivoting element after partitioning
    int partition(std::vector<T>& data, int left, int right) {
        T pivot = choose_index(data, left, right);
        size_t pivot_ind = std::find(data.begin() + left, data.begin() + right + 1, pivot) - data.begin();

        std::swap(data[right], data[pivot_ind]);

        int i = left;

        for (int j = left; j < right; j++) {
            if (data[j] <= pivot) {
                std::swap(data[i], data[j]);
                i++;
            }
        }

        std::swap(data[i], data[right]);

        return i;
    }

    /// @brief Chooses a pivoting element based on the median of medians algorithm
    /// @param data vector of elements
    /// @param left left boundary of subarray
    /// @param right right boundary
    /// @return pivoting element
    T choose_index(std::vector<T>& data, size_t left, size_t right) const {
        if (right - left + 1 <= 5) {
            return data[left + (right - left) / 2];
        }

        std::vector<T> medians;

        for (int i = left; i + 4 <= right; i += 5) {
            sort_5(data, i, i + 4);
            medians.push_back(data[i + 2]);
        }

        return choose_index(medians, 0, medians.size() - 1);
    }

    /// @brief A sorting network algorithm that sorts a 5 element array in 7 comparisons
    /// @param data full vector to be sorted
    /// @param left left boundary of the group of 5 elements
    /// @param right right boundary
    void sort_5(std::vector<T>& data, size_t left, size_t right) const {
        assert(right - left == 4);
        std::vector<T> result(data.begin() + left, data.begin() + right + 1);
        if (result[0] > result[1]) {
            std::swap(result[0], result[1]);
        }
        if (result[2] > result[3]) {
            std::swap(result[2], result[3]);
        }
        if (result[0] > result[2]) {
            std::swap(result[0], result[2]);
            std::swap(result[1], result[3]);
        }

        if (result[4] > result[2]) {
            if (result[4] > result[3]) {// case 1: A C D E
                if (result[1] > result[3]) {
                    if (result[1] > result[4]) {
                        result = { result[0], result[2], result[3], result[4], result[1] };
                    }
                    else {
                        result = { result[0], result[2], result[3], result[1], result[4] };
                    }
                }
                else if (result[1] < result[2]) {
                    result = { result[0], result[1], result[2], result[3], result[4] };
                }
                else {
                    result = { result[0], result[2], result[1], result[3], result[4] };
                }
            }
            else { // case 2 A C E D
                if (result[1] > result[4]) {
                    if (result[1] > result[3]) {
                        result = { result[0], result[2], result[4], result[3], result[1] };
                    }
                    else {
                        result = { result[0], result[2], result[4], result[1], result[3] };
                    }
                }
                else if (result[1] < result[2]) {
                    result = { result[0], result[1], result[2], result[4], result[3] };
                }
                else {
                    result = { result[0], result[2], result[1], result[4], result[3] };
                }
            }
        }
        else if (result[4] < result[0]) { // subcase 1 E A C D
            if (result[1] > result[2]) {
                if (result[1] > result[3]) {
                    result = { result[4], result[0], result[2], result[3], result[1] };
                }
                else {
                    result = { result[4], result[0], result[2], result[1], result[3] };
                }
            }
            else {
                result = { result[4], result[0], result[1], result[2], result[3] };
            }
        }
        else { // subcase 2 A E C D
            if (result[1] > result[2]) {
                if (result[1] > result[3]) {
                    result = { result[0], result[4], result[2], result[3], result[1] };
                }
                else {
                    result = { result[0], result[4], result[2], result[1], result[3] };
                }
            }
            else if (result[1] < result[4]) {
                result = { result[0], result[1], result[4], result[2], result[3] };
            }
            else {
                result = { result[0], result[4], result[1], result[2], result[3] };
            }
        }

        for (int i = left; i <= right; i++) {
            data[i] = result[i - left];
        }
    }


    std::random_device rd;
    std::mt19937 gen;
};

#endif
---------------------------------------------------------------------------------
---------------------------------heap_sorter.cpp---------------------------------
#pragma once

#ifndef HEAP_SORTER_CPP

#include "Sorter.cpp"
#include "Data_structures/heap.cpp"
#include <vector>

template<class T>
class HeapSorter : public Sorter<T> {
public:
    HeapSorter() : Sorter<T>(1e6, "Heap sort") {}

    void sort(std::vector<T>& data, int l, int r) override {
        Heap heap(data);
        data = std::move(heap.get_sorted());
    }

private:

};

#endif
---------------------------------------------------------------------------------
---------------------------------insertion_bin_sorter.cpp------------------------
#pragma once

#ifndef INSERTION_BIN_SORTER_CPP

#include "Sorter.cpp"
#include <vector>

template<class T>
class InsertionBinSorter : public Sorter<T> {
public:
    InsertionBinSorter() : Sorter<T>(1e5, "Binary insertion sort") {}

    void sort(std::vector<T>& data, int l, int r) override {
        for (int i = 1; i < data.size(); ++i) {
            T value = data[i];
            int index = std::upper_bound(data.begin(), data.begin() + i, value) - data.begin();

            for (int j = i; j > index; j--) {
                std::swap(data[j], data[j - 1]);
            }
        }
    }

private:

};

#endif
---------------------------------------------------------------------------------
---------------------------------insertion_sorter.cpp----------------------------
#pragma once

#ifndef INSERTION_SORTER_CPP

#include "Sorter.cpp"
#include <vector>

template<class T>
class InsertionSorter : public Sorter<T> {
public:
    InsertionSorter() : Sorter<T>(1e5, "Insertion sort") {}

    void sort(std::vector<T>& data, int l, int r) override {
        for (int i = 1; i < data.size(); ++i) {
            int index = i - 1;
            T value = data[i];

            for (; index >= 0 && data[index] > value; index--) {
                data[index + 1] = data[index];
            }

            data[index + 1] = value;
        }
    }

private:

};

#endif
---------------------------------------------------------------------------------
---------------------------------merge_sorter.cpp--------------------------------
#pragma once

#ifndef MERGE_SORTER_CPP

#include "Sorter.cpp"
#include <vector>

template<class T>
class MergeSorter : public Sorter<T> {
public:
    MergeSorter() : Sorter<T>(1e6, "Merge sort") {}

    void sort(std::vector<T>& data, int l, int r) override {
        int n = data.size();

        for (int curr_size = 1; curr_size < n; curr_size *= 2) {
            for (int l = 0; l < n - 1; l += 2 * curr_size) {
                int mid = std::min(l + curr_size - 1, n - 1);
                int r = std::min(l + 2 * curr_size - 1, n - 1);
                merge(data, l, mid, r);
            }
        }
    }

private:
    /// @brief merges two subarrays in ascending order
    /// @param data vector of elements
    /// @param l left boundary of first subarray
    /// @param mid right boundary of first subarray, left boundary of second subarray
    /// @param r right boundary of second subarray
    void merge(std::vector<T>& data, int l, int mid, int r) {
        int left_size = mid - l + 1;
        int right_size = r - mid;

        std::vector<T> left(data.begin() + l, data.begin() + mid + 1);
        std::vector<T> right(data.begin() + mid + 1, data.begin() + r + 1);

        int i = 0, j = 0, k = l;

        while (i < left_size && j < right_size) {
            if (left[i] <= right[j]) {
                data[k++] = left[i++];
            } else {
                data[k++] = right[j++];
            }
        }

        while (i < left_size) {
            data[k++] = left[i++];
        }

        while (j < right_size) {
            data[k++] = right[j++];
        }
    }
};

#endif
---------------------------------------------------------------------------------
---------------------------------quick_sorter.cpp--------------------------------
#pragma once

#ifndef QUICK_SORTER_CPP

#include "Sorter.cpp"
#include <vector>
#include <random>

template<class T>
class QuickSorter : public Sorter<T> {
public:
    QuickSorter() : Sorter<T>(1e6, "Quick sort") {}

    void sort(std::vector<T>& data, int l, int r) override {
        if (l >= r) {
            return;
        }

        int part = partition(data, l, r);

        sort(data, l, part - 1);
        sort(data, part + 1, r);
    }

private:
    /// @brief Function needed by quick sort to partition an array based on the pivoting element
    /// @param data full vector to be sorted
    /// @param left left boundary of the "to be sorted" subarray
    /// @param right right boundary
    /// @return the index of the pivoting element after partitioning
    int partition(std::vector<T>& data, int left, int right) {
        T pivot = 0LL + data[left] + data[right] + data[(right + left) / 2] - 
            std::max(data[left], std::max(data[right], data[(right + left) / 2])) - std::min(data[left], std::min(data[right], data[(right + left) / 2]));
        
        int pivot_ind = left;
        //T pivot = data[pivot_ind];

        if (pivot == data[right]) {
            pivot_ind = right;
        }
        else if (pivot == data[(right + left) / 2]) {
            pivot_ind = (right + left) / 2;
        }

        std::swap(data[right], data[pivot_ind]);

        int i = left;

        for (int j = left; j < right; j++) {
            if (data[j] <= pivot) {
                std::swap(data[i], data[j]);
                i++;
            }
        }

        std::swap(data[i], data[right]);

        return i;
    }
};

#endif
---------------------------------------------------------------------------------
---------------------------------skip_list_sorter.cpp----------------------------
#pragma once

#ifndef SKIP_LIST_SORTER_CPP

#include "Sorter.cpp"
#include "Data_structures/skip_list.cpp"
#include <vector>

template<class T>
class SkipListSorter : public Sorter<T> {
public:
    SkipListSorter() : Sorter<T>(3e5, "Skip list sort") {}

    void sort(std::vector<T>& data, int l, int r) override {
        SkipList<T> list = list_from_vector<T>(data);
        data = vector_from_skip_list<T>(list);
    }

private:

};

#endif
---------------------------------------------------------------------------------
---------------------------------sorter.cpp--------------------------------------
#pragma once
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")

#ifndef SORTER_CPP

#include <vector>
#include <cstddef>
#include <string>
#include <limits>

/// @brief An interface class of sorting engines, which specifies attributes neccessary for its work
/// @tparam T data type of "to be sorted" elements
template<class T>
class Sorter {
public:
    Sorter<T>(size_t value, std::string name): max_test_size(value), sort_name(name) {}
    virtual void sort(std::vector<T>& data, int l, int r) = 0;

    size_t get_max_test_size() const {
        return max_test_size;
    }

    std::string get_sort_name() const {
        return sort_name;
    }

private:
    size_t max_test_size;
    std::string sort_name;
};

#endif
---------------------------------------------------------------------------------
---------------------------------sorters_list.hpp--------------------------------
#pragma once

#ifndef SORTERS_LIST_HPP

#include "bubble_sorter.cpp"
#include "merge_sorter.cpp"
#include "insertion_sorter.cpp"
#include "quick_sorter.cpp"
#include "heap_sorter.cpp"
#include "g_quick_sorter.cpp"
#include "insertion_bin_sorter.cpp"
#include "skip_list_sorter.cpp"

#endif
---------------------------------------------------------------------------------
---------------------------------benchmark.cpp-----------------------------------
#pragma once

#ifndef BENCHMARK_CPP

#include "src/Sorter.cpp"

#include <concepts>
#include <random>
#include <algorithm>
#include <assert.h>

#include <limits>
#include <chrono>

#include <iostream>
#include <iomanip>
#include <fstream>

template<class T>
class Benchmark {
public:
    Benchmark(Sorter<T>* sorting_engine): sorting_engine(sorting_engine), gen(rd()) {
        std::string file_name = sorting_engine->get_sort_name() + ".txt";
        
        if constexpr(std::is_integral_v<T>) {
            test_sizes = {10, 30, 100, 300, 1000, 3000, 10000, 30000, 100000, 300000, 1000000};
            fout = std::ofstream("benchmark_results/Int_" + file_name);
        }
        else if constexpr(std::is_same_v<T, std::string>) {
            test_sizes = {10, 30, 100, 300, 1000, 3000, 10000};
            lengths = {1, 10, 100, 1000, 10000};
            fout = std::ofstream("benchmark_results/String_" + file_name);
        }
    }

    /// @brief Tests the time of sorting on different times. Prints a nice table to stdin and file as well.
    void test() {
        if constexpr (std::is_integral_v<T>) {
            std::cout << std::setw(23) << sorting_engine->get_sort_name() << std::endl;
            std::cout << "|" << std::setw(7) << "N" << "|" << std::setw(15) << "Time taken" << "|" << std::endl;

            for (const auto& test_size : test_sizes) {
                std::cout << "|" << std::setw(7) << test_size << "|";

                if (sorting_engine->get_max_test_size() >= test_size) {
                    auto result = test_one_size(test_size);
                    std::cout << std::setw(15) << convert_time(result) << "|" << std::endl;
                    fout << "N:" << test_size << " " << result << std::endl;
                }
                else {
                    std::cout << std::setw(15) << ">5s" << "|" << std::endl;
                    fout << "N:" << test_size << " " << ">5s" << std::endl;
                }

                assert(std::is_sorted(test_data.begin(), test_data.end()) && "Array was sorted incorrectly");
            }
        }

        else if constexpr (std::is_same_v<T, std::string>) {
            std::cout << std::setw(23) << sorting_engine->get_sort_name() << std::endl;

            std::cout << "|" << std::setw(7) << "M \\ N" << "|";
            for (auto& test_size : test_sizes) {
                std::cout << std::setw(15) << test_size << "|";
            }
            std::cout << std::endl;

            for (auto& string_size : lengths) {
                std::cout << "|" << std::setw(7) << string_size << "|";
                
                for (auto& test_size : test_sizes) {
                    if (sorting_engine->get_max_test_size() >= test_size) {
                        auto result = test_one_size(test_size, string_size);
                        std::cout << std::setw(15) << convert_time(result) << "|";
                        fout << "(N: " << test_size << " M: " << string_size << ") " << result << std::endl;
                    }
                    else {
                        std::cout << std::setw(15) << ">5s" << "|";
                        fout << "(N: " << test_size << " M: " << string_size << ") " << ">5s" << std::endl;
                    }
                    assert(std::is_sorted(test_data.begin(), test_data.end()) && "Array was sorted incorrectly");
                }
                std::cout << std::endl;
            }
        }
    }

private:
    /// @brief Tests the performance of the used sorting engine on a chosen test size
    /// @param test_size Testing array size
    /// @param string_size In case of elements being strings, the length of strings
    /// @param runs Number of runs to average out performance
    /// @return Average time of execution
    int64_t test_one_size(size_t test_size, size_t string_size = 0, int runs = 10) {
        int64_t result = 0;

        for (int i = 0; i < runs; i++) {
            result += time_test(test_size, string_size);
            
        }

        return result / runs;
    }

    /// @brief Measures the execution time of one run
    /// @param test_size Array size
    /// @param string_size If elements are strings, the string length
    /// @return The time taken by the sorting engine
    int64_t time_test(size_t test_size, size_t string_size = 0) {
        test_data = generate_test(test_size, string_size);

        auto start = std::chrono::high_resolution_clock::now();
        sorting_engine->sort(test_data, 0, test_size - 1);
        auto end = std::chrono::high_resolution_clock::now();

        int64_t result = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        //std::cout << result << std::endl;

        return result;
    }

    /// @brief Generates a random array of elements
    /// @param test_size Array size
    /// @param string_size If the elements are strings, generates strings this size
    /// @return Generated test array
    std::vector<T> generate_test(size_t test_size, size_t string_size = 0) {
        if constexpr(std::is_integral_v<T>) {
            T min_value = std::numeric_limits<T>::min();
            T max_value = std::numeric_limits<T>::max();

            std::uniform_int_distribution dis(min_value, max_value);

            std::vector<T> arr(test_size);
            for (auto& it : arr) {
                it = dis(gen);
            }

            return arr;
        }
        else if constexpr(std::is_same_v<T, std::string>) {
            std::vector<T> arr(test_size);
            std::uniform_int_distribution<int> dis(0, 25);

            for (auto &it : arr) {
                T current = std::string(string_size, 'a');
                for (auto& ch : current) {
                    ch += dis(gen);
                }
                it = current;
            }

            return arr;
        }
    }

    /// @brief Function to convert time to mcs/ms/s depending on the value of time
    /// @param time Time in nanoseconds
    /// @return String representation of time value
    std::string convert_time(int64_t time) const {
        if (time < 1000) {
            return std::to_string(time) + " ns";
        }
        else if (time < 1e6) {
            return std::to_string(std::round(time / 1e3 * 1e3) / 1000) + " mcs";
        }
        else if (time < 1e9) {
            return std::to_string(std::round(time / 1e6 * 1e6) / 1000000) + " ms";
        }
        return std::to_string(std::round(time / 1e9 * 1e9) / 1000000000) + " s";
    }

    std::random_device rd;
    std::mt19937 gen;

    Sorter<T>* sorting_engine;
    std::vector<T> test_data;
    std::vector<size_t> test_sizes;
    std::vector<size_t> lengths;
    std::ofstream fout;
};

#endif
---------------------------------------------------------------------------------
---------------------------------collect_data.cpp--------------------------------
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

#include "src/sorters_list.hpp"
#include "Benchmark.cpp"

#include <iostream>

int main() {
    std::vector<Sorter<int>*> int_sorters = {
        new InsertionSorter<int>,
        new MergeSorter<int>,
        new QuickSorter<int>,
        new HeapSorter<int>,
        new GQuickSorter<int>,
        new SkipListSorter<int>
    };
    for (auto& it : int_sorters) {
        Benchmark<int> bench(it);

        bench.test();
    }

    std::vector<Sorter<std::string>*> string_sorters = {
        new InsertionSorter<std::string>,
        new InsertionBinSorter<std::string>
    };

    for (auto& it : string_sorters) {
        Benchmark<std::string> bench(it);

        bench.test();
    }
    return 0;
}
---------------------------------------------------------------------------------