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

Answer 1

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.

Answer 2

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

Answer 3

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)

• Cody Gray: 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. :-)
• coderodde: Insertion sort is \$\Theta(n^2)\$ in average and worst cases.