algorithms.hpp

Go to the documentation of this file.

 
#pragma once
 
#include <algorithm>
#include <cstdint>
#include <numeric>
#include <vector>

 
namespace algorithms {
 
// ─── Sorting ─────────────────────────────────────────────────────────────────

template <typename T>
void bubble_sort(std::vector<T>& data) {
    bool swapped;
    for (std::size_t i = 0; i < data.size(); ++i) {
        swapped = false;
        for (std::size_t j = 0; j + 1 < data.size() - i; ++j) {
            if (data[j + 1] < data[j]) {
                std::swap(data[j], data[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

template <typename T>
void insertion_sort(std::vector<T>& data) {
    for (std::size_t i = 1; i < data.size(); ++i) {
        T key = data[i];
        std::size_t j = i;
        while (j > 0 && key < data[j - 1]) {
            data[j] = data[j - 1];
            --j;
        }
        data[j] = key;
    }
}
 
// ─── Numeric ─────────────────────────────────────────────────────────────────

inline std::uint64_t fibonacci(unsigned n) {
    if (n <= 1) return n;
    std::uint64_t a = 0, b = 1;
    for (unsigned i = 2; i <= n; ++i) {
        std::uint64_t c = a + b;
        a = b;
        b = c;
    }
    return b;
}

inline unsigned gcd(unsigned a, unsigned b) {
    while (b != 0) {
        unsigned t = b;
        b = a % b;
        a = t;
    }
    return a;
}

inline bool is_prime(unsigned n) {
    if (n < 2) return false;
    if (n < 4) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (unsigned i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

template <typename T>
T sum(const std::vector<T>& data) {
    return std::accumulate(data.begin(), data.end(), T{});
}
 
} // namespace algorithms
 // end of algorithms group