Insertion sort C++14 implementation

Question

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 <iostream>
#include <vector>

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

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

    std::vector<int> 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<int> &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<int> &v) {
    for (const auto &i : v) {
        std::cout << i << " ";
    }
    std::cout << "\n";
}

coderodde · Accepted Answer · 2017-01-15 10:59:58Z

Advice 1

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

Advice 2

Making your insertion sort generic is easy:

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

Advice 3

Making your print function generic is not hard either:

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

Hope that helps.

Richard Hodges · Accepted Answer · 2017-01-15 15:44:28Z

A few things to think about:

1. Sorting in terms of iterators, and allowing a customisable predicate is more 'standard-like':

template<class Iter, class Pred = std::less<> >
void insertionSort(Iter first, Iter last, Pred pred = Pred())
{
    for (auto i = first; i != last; i = std::next(i)) {
        std::rotate(std::upper_bound(first, i, *i, pred), i, std::next(i));
    }
}

2. Why not also provide a range-like interface?:

template<class Container, class Pred = std::less<>>
Container& insertionSort(Container&& cont, Pred pred = Pred())
{
    insertionSort(std::begin(cont), std::end(cont), std::forward<Pred>(pred));
    return cont;
}

3. Why not provide an iomanip-like function to provide printing of vectors in a structured way:

template<class T, class A>
struct vector_printer
{
    std::ostream& operator()(std::ostream& os) const {
        const char* sep = "";
        const char* pre_brace = "";
        os << "[";
        for (auto&& e : vec_) {
            os << sep << e;
            sep = ", ";
            pre_brace = " ";
        }
        return os << pre_brace << "]";
    }

    const std::vector<T, A>& vec_;
};
template<class T, class A>
decltype(auto) operator<<(std::ostream& os, vector_printer<T, A> const& p)
{
    return p(os);
}

template<class T, class A>
auto print(std::vector<T, A> const& v)
{
    return vector_printer<T, A> { v };
}

This then allows us to write expressive code:

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

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

    // Print the vector before sorting.
    std::cout << print(v) << std::endl;

    // Print the vector after sorting.
    std::cout << print(insertionSort(v)) << std::endl;

    // ascending order
    std::cout << print(insertionSort(v, std::greater<>())) << std::endl;

    return 0;
}

Complete code:

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

template<class Iter, class Pred = std::less<> >
void insertionSort(Iter first, Iter last, Pred pred = Pred())
{
    for (auto i = first; i != last; i = std::next(i)) {
        std::rotate(std::upper_bound(first, i, *i, pred), i, std::next(i));
    }
}

template<class Container, class Pred = std::less<>>
Container& insertionSort(Container&& cont, Pred pred = Pred())
{
    insertionSort(std::begin(cont), std::end(cont), std::forward<Pred>(pred));
    return cont;
}

template<class T, class A>
struct vector_printer
{
    std::ostream& operator()(std::ostream& os) const {
        const char* sep = "";
        const char* pre_brace = "";
        os << "[";
        for (auto&& e : vec_) {
            os << sep << e;
            sep = ", ";
            pre_brace = " ";
        }
        return os << pre_brace << "]";
    }

    const std::vector<T, A>& vec_;
};
template<class T, class A>
decltype(auto) operator<<(std::ostream& os, vector_printer<T, A> const& p)
{
    return p(os);
}

template<class T, class A>
auto print(std::vector<T, A> const& v)
{
    return vector_printer<T, A> { v };
}

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

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

    // Print the vector before sorting.
    std::cout << print(v) << std::endl;
    // Sort

    // Print the vector after sorting.
    std::cout << print(insertionSort(v)) << std::endl;

    // ascending order
    std::cout << print(insertionSort(v, std::greater<>())) << std::endl;

    // sort now works on any container:

    std::cout << insertionSort(std::string("ZXCVBNMASDFGHJKLQWERTYUIOP")) << std::endl;
    return 0;
}

Expected output:

[10, 9, 8, 7, 6, 5, 4, 3, 2, 1 ]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1 ]
ABCDEFGHIJKLMNOPQRSTUVWXYZ

Babra Cunningham · Accepted Answer · 2017-01-15 10:39:06Z

-2

Your code looks fine, but it has a run time complexity of O(n*n), you can perform this in logarithmic time:

std::vector<int> to_insert_sort {2,3,5,6,1,1,3,2};

int to_insert {3};

std::sort(to_insert_sort.begin(), to_insert_sort.end()); //Log

auto pos = std::upper_bound(to_insert_sort.begin(), to_insert_sort.end(), 5); //Log

to_insert_sort.insert(pos, to_insert); //O(n)

edited Jan 15, 2017 at 10:39

answered Jan 15, 2017 at 10:33

Babra Cunningham

2443 silver badges12 bronze badges

1

\$\begingroup\$ std::sort is going to be O(n*log n), so still an order of magnitude better than the original O(n^2), but not nearly as good as the advertised logarithmic. :-) \$\endgroup\$

Cody Gray
– Cody Gray

2017-01-15 17:59:06 +00:00
Commented Jan 15, 2017 at 17:59
3

\$\begingroup\$ Insertion sort is \$\Theta(n^2)\$ in average and worst cases. \$\endgroup\$

coderodde
– coderodde

2017-01-15 18:35:04 +00:00
Commented Jan 15, 2017 at 18:35

Add a comment |

Stack Exchange Network

Insertion sort C++14 implementation

3 Answers 3

1. Sorting in terms of iterators, and allowing a customisable predicate is more 'standard-like':

2. Why not also provide a range-like interface?:

3. Why not provide an iomanip-like function to provide printing of vectors in a structured way:

This then allows us to write expressive code:

Complete code:

Expected output:

You must log in to answer this question.

Hot Network Questions

Insertion sort C++14 implementation

3 Answers 3

1. Sorting in terms of iterators, and allowing a customisable predicate is more 'standard-like':

2. Why not also provide a range-like interface?:

3. Why not provide an iomanip-like function to provide printing of vectors in a structured way:

This then allows us to write expressive code:

Complete code:

Expected output:

You must log in to answer this question.

Related

Hot Network Questions