sorting algorithms, heh.

insertion_sort.cpp

#include <iostream>
#include <algorithm>
#include <vector>
#include <array>

template <typename RandomIt>
void insertion_sort(RandomIt begin, RandomIt end)
{
    // loop through all the elements, from
    // the the second element to the last. 
    // As we are assuming the first element is the minimum
    for(RandomIt it = begin + 1; it != end; ++it)
    {
        // go from where we are to the beginning of the array
        // i.e. loop through the 'sorted' array backwards
        for(RandomIt jt = it; jt != begin; --jt)
        {
            // if the previous element is larger than the
            // current elemenet we're looking at
            if(*(jt - 1) > *jt)
            {
                // then we should swap
                std::swap(*jt, *(jt - 1));
            }
            // otherwise, we've reached a point where we
            // no longer need to swap, and thus
            else
            {
                // we should break
                break;
            }
        }
    }
}


int main(int argc, char *argv[])
{
    // using vector
    std::cout << "using std::vector\n";
    {
        std::vector<int> numbers = { 32, 5, 65, 3, 3, 95, 1 };

        std::cout << "unsorted array:\n";
        for(auto& x : numbers) std::cout << x << ' ';
        std::cout << '\n';

        insertion_sort(numbers.begin(), numbers.end());

        std::cout << "sorted array:\n";
        for(auto& x : numbers) std::cout << x << ' ';
        std::cout << '\n';
    }

    std::cout << '\n';

    // using std::array
    std::cout << "using std::array\n";
    {
        std::array<int, 5> numbers = { -53, 343, 3, 5, 5 };

        std::cout << "unsorted array:\n";
        for(auto& x : numbers) std::cout << x << ' ';
        std::cout << '\n';

        insertion_sort(numbers.begin(), numbers.end());

        std::cout << "sorted array:\n";
        for(auto& x : numbers) std::cout << x << ' ';
        std::cout << '\n';
    }

    return 0;
}

selection_sort.cpp

#include <iostream>
#include <algorithm>
#include <vector>
#include <array>

template <typename RandomIt>
void selection_sort(RandomIt begin, RandomIt end)
{
    // loop through the first and n - 1 elements
    // since the last element will be sorted correctly
    for(RandomIt it = begin; it != end - 1; ++it)
    {
        // assume the current element we're at is the minimum
        RandomIt min = it;
        // loop through the 'unsorted' section
        for(RandomIt it = min + 1; it != end; ++it)
        {
            // if we find a smaller value than what we
            // currently have, update the minimum
            if(*it < *min)
            {
                min = it;
            }
        }

        // if we actually found a new miniumum value
        if(min != it)
        {
            // swap it with the old assumed minimum
            std::swap(*it, *min);
        }
    }
}


int main(int argc, char *argv[])
{
    // using vector
    std::cout << "using std::vector\n";
    {
        std::vector<int> numbers = { 32, 5, 65, 3, 3, 95, 1 };

        std::cout << "unsorted array:\n";
        for(auto& x : numbers) std::cout << x << ' ';
        std::cout << '\n';

        selection_sort(numbers.begin(), numbers.end());

        std::cout << "sorted array:\n";
        for(auto& x : numbers) std::cout << x << ' ';
        std::cout << '\n';
    }

    std::cout << '\n';

    // using std::array
    std::cout << "using std::array\n";
    {
        std::array<int, 5> numbers = { -53, 343, 3, 5, 5 };

        std::cout << "unsorted array:\n";
        for(auto& x : numbers) std::cout << x << ' ';
        std::cout << '\n';

        selection_sort(numbers.begin(), numbers.end());

        std::cout << "sorted array:\n";
        for(auto& x : numbers) std::cout << x << ' ';
        std::cout << '\n';
    }

    return 0;
}