HiveBrain v1.2.0
Get Started
← Back to all entries
snippetcppMinor

Insertion sort C++14 implementation

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
insertionimplementationsort

Problem

I have implemented insertion sort using C++. Is there any way to improve my code and is it CppCoreGuideline compliant? As I passed the vector as const in print method, do I need to specify const in range for loop?

/*
 *  Insertion Sort
 */

#include 
#include 

void insertionSort(std::vector &v);
void print(const std::vector &v);

int main()
{
    std::ios_base::sync_with_stdio(false);

    std::vector v {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

    // Print the vector before sorting.
    print(v);
    // Sort
    insertionSort(v);
    // Print the vector after sorting.
    print(v);

    return 0;
}

void insertionSort(std::vector &v) {
    for (auto i = v.begin() + 1; i != v.end(); ++i) {
        int key = *i;

        auto j = i - 1;
        while (j >= v.begin() && *j > key) {
            *(j+1) = *j;
            --j;
        }
        *(j+1) = key;
    }
    return;
}

void print(const std::vector &v) {
    for (const auto &i : v) {
        std::cout << i << " ";
    }
    std::cout << "\n";
}

Solution

Advice 1

In your insertionSort you can remove the last statement (return).

Advice 2

Making your insertion sort generic is easy:

template
void insertion_sort(RandIt begin, RandIt end)
{
    for (auto i = begin + 1; i != end; ++i)
    {
        auto key = *i;
        auto j = i - 1;

        while (j >= begin and *j > key)
        {
            *(j + 1) = *j;
            --j;
        }

        *(j + 1) = key;
    }
}

template
void insertion_sort(Container& cont)
{
    insertion_sort(std::begin(cont), std::end(cont));
}


Advice 3

Making your print function generic is not hard either:

template
void print(RandIt begin, RandIt end)
{
    using value_type = typename std::iterator_traits::value_type;
    std::copy(begin, end, std::ostream_iterator(std::cout, ", "));
    std::cout 
void print(const Container& container)
{
    print(std::begin(container), std::end(container));
}


Hope that helps.

Code Snippets

template<typename RandIt>
void insertion_sort(RandIt begin, RandIt end)
{
    for (auto i = begin + 1; i != end; ++i)
    {
        auto key = *i;
        auto j = i - 1;

        while (j >= begin and *j > key)
        {
            *(j + 1) = *j;
            --j;
        }

        *(j + 1) = key;
    }
}

template<typename Container>
void insertion_sort(Container& cont)
{
    insertion_sort(std::begin(cont), std::end(cont));
}
template<typename RandIt>
void print(RandIt begin, RandIt end)
{
    using value_type = typename std::iterator_traits<RandIt>::value_type;
    std::copy(begin, end, std::ostream_iterator<value_type>(std::cout, ", "));
    std::cout << std::endl;
}

template<typename Container>
void print(const Container& container)
{
    print(std::begin(container), std::end(container));
}

Context

StackExchange Code Review Q#152687, answer score: 6

Revisions (0)

No revisions yet.