4
\$\begingroup\$

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";
}
\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
-1
\$\begingroup\$

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)
\$\endgroup\$
  • 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 Jan 15 '17 at 17:59
  • 3
    \$\begingroup\$ Insertion sort is \$\Theta(n^2)\$ in average and worst cases. \$\endgroup\$ – coderodde Jan 15 '17 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.