algorithms Namespace Reference

Functions
template<typename T>
void	bubble_sort (std::vector< T > &data)
	Sort a vector in-place using bubble sort.
std::uint64_t	fibonacci (unsigned n)
	Compute the \(n\)-th Fibonacci number.
unsigned	gcd (unsigned a, unsigned b)
	Compute the greatest common divisor of two integers.
template<typename T>
void	insertion_sort (std::vector< T > &data)
	Sort a vector in-place using insertion sort.
bool	is_prime (unsigned n)
	Test whether a number is prime.
template<typename T>
T	sum (const std::vector< T > &data)
	Compute the sum of all elements in a range.

Function Documentation

bubble_sort()

template<typename T>

void algorithms::bubble_sort

(

std::vector< T > &

data

)

Sort a vector in-place using bubble sort.

Repeatedly steps through the list, swaps adjacent elements that are out of order, and repeats until no swaps are needed.

Complexity:

\[ \text{Time: } O(n^2), \qquad \text{Space: } O(1) \]

Template Parameters

T	Element type (must support operator<).

Parameters

data	The vector to sort.

Note

This is for demonstration only. Use std::sort in production.

See also

insertion_sort for a slightly better quadratic sort.

containers::Stack for a container that could hold sorted results.

Definition at line 56 of file algorithms.hpp.

                                     {
    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;
    }
}

fibonacci()

std::uint64_t algorithms::fibonacci ( unsigned n )

inline

Compute the \(n\)-th Fibonacci number.

Uses the recurrence:

\[ F(n) = F(n-1) + F(n-2), \quad F(0) = 0, \; F(1) = 1 \]

Implemented iteratively for \(O(n)\) time and \(O(1)\) space.

Parameters

n	The index (0-based).

Returns

\(F(n)\).

Invariant

The result is always non-negative.

Bug

Overflows for n > 93 when using uint64_t.

Definition at line 119 of file algorithms.hpp.

                                         {
    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;
}

gcd()

unsigned algorithms::gcd ( unsigned a, unsigned b )

inline

Compute the greatest common divisor of two integers.

Uses the Euclidean algorithm:

\[ \gcd(a, 0) = a, \qquad \gcd(a, b) = \gcd(b, \; a \bmod b) \]

Parameters

a	First integer.
b	Second integer.

Returns

\(\gcd(a, b)\).

Precondition

Both arguments should be non-negative.

Postcondition

The return value divides both a and b.

Deprecated

Use std::gcd from <numeric> (C++17) instead.

Definition at line 147 of file algorithms.hpp.

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

insertion_sort()

template<typename T>

void algorithms::insertion_sort

(

std::vector< T > &

data

)

Sort a vector in-place using insertion sort.

Builds the sorted portion one element at a time by inserting each new element into its correct position.

Complexity:

\[ \text{Best: } O(n), \quad \text{Average/Worst: } O(n^2), \quad \text{Space: } O(1) \]

Template Parameters

T	Element type (must support operator<).

Parameters

data	The vector to sort.

Attention

Insertion sort is efficient for small or nearly-sorted data. For large datasets, prefer std::sort ( \(O(n \log n)\)).

Definition at line 88 of file algorithms.hpp.

                                        {
    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;
    }
}

is_prime()

bool algorithms::is_prime ( unsigned n )

inline

Test whether a number is prime.

Uses trial division up to \(\sqrt{n}\):

\[ \text{Time: } O(\sqrt{n}) \]

Parameters

n	The number to test.

Returns

true if n is prime, false otherwise.

Test

Verify edge cases: is_prime(0) == false, is_prime(1) == false, is_prime(2) == true, is_prime(97) == true.

Definition at line 170 of file algorithms.hpp.

                                 {
    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;
}

sum()

template<typename T>

T algorithms::sum

(

const std::vector< T > &

data

)

Compute the sum of all elements in a range.

Template Parameters

T	Numeric type.

Parameters

data	The input vector.

Returns

The sum \(\sum_{i=0}^{n-1} \text{data}[i]\).

See also

yoda::Vec2::dot for a related inner-product operation.

Definition at line 190 of file algorithms.hpp.

                                {
    return std::accumulate(data.begin(), data.end(), T{});
}