Insertion Sorting in C++

Question

From Wikipedia:

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

Sorting is typically done in-place, by iterating up the array, growing the sorted list behind it. At each array-position, it checks the value there against the largest value in the sorted list (which happens to be next to it, in the previous array-position checked). If larger, it leaves the element in place and moves to the next. If smaller, it finds the correct position within the sorted list, shifts all the larger values up to make a space, and inserts into that correct position.

Just tried out my solution in C++:

#include <vector>
std::vector<int> ins_sort(std::vector<int> series)
{
 for(int i=1; i<series.size(); i++)
 {
 int key = series[i];
 for(int j=i-1; j>-1; j--)
 {
 if (key < series[j])
 {
 series[j+1] = series[j];
 series[j] = key;
 }
 else break;
 }
 }
 return series;
}

Answer 1

I wouldn't recommend passing and returning the vector by value. Pass by reference, and do not return at all - typically sorting is done in place anyway.

Another generic advice: no raw loops. The internal loop does some important job, which has to be realized and given a proper name, insert perhaps.

typedef std::vector<int>::size vsize_t;
void ins_sort(std::vector<int> & series)
{
 for(vsize_t i=1; i < series.size(); i++)
 {
 insert(series, i, series[i]);
 }
}
void insert(std::vector<int> & series, vsize_t last, int key)
{
 for (vsize_t j = last - 1; j > -1; --j)
 {
 if (key < series[j]) {
 series[j + 1] = series[j];
 series[j] = key;
 }
 else
 break;
 }
}

Now it is possible to simplify the logic by eliminating j, and combining the two condition checks together:

void insert(std::vector<int> & series, vsize_t last, int key)
{
 while ((--last > -1) && (key < series[last]))
 {
 series[last + 1] = series[last];
 series[last] = key;
 }
}

You can see how the series[last] = key; assignment is rather redundant - it will necessarily be overwritten at the next iteration, so it only makes sense only at the last one:

void insert(std::vector<int> & series, vsize_t last, int key)
{
 while ((--last > -1) && (key < series[last]))
 {
 series[last + 1] = series[last];
 }
 series[last] = key;
}

Testing two conditions at every iteration is expensive. You may notice that the first condition only strikes if key is less than all the elements, in other words, it is less than series[0] (it is sorted up to the point already):

void insert(std::vector<int> & series, vsize_t last, int key)
{
 if (key < series[0]) {
 while (last-- > 0) {
 series[last+1] = series[last];
 }
 } else {
 while (key < series[last])
 {
 series[last+1] = series[last];
 }
 }
 series[last] = key;
}

and applying the rule one more time, we see that the first loop does shift right by 1, and the second does unguarded shift right by one.

Combining everything, we are getting:

typedef std::vector<int>::size vsize_t;
vsize_t unguarded_shift(std::vector<int> & series, vsize_t last, int key)
{
 while (key < series[last--])
 {
 series[last + 1] = series[last];
 }
 return last;
}
vsize_t shift(std::vector<int> & series, vsize_t last)
{
 while (last-- > 0) {
 series[last+1] = series[last];
 }
 return last;
}
void insert(std::vector<int> & series, vsize_t last, int key)
{
 if (key < series[0]) {
 last = shift(series, last);
 } else {
 last = unguarded_shift(series, last, key);
 }
 series[last] = key;
}
void ins_sort(std::vector<int> & series)
{
 for(vsize_t i=1; i < series.size(); i++)
 {
 insert(series, i, series[i])
 }
}

• David Harkness: And if you have indented code that needs another level, just place an x in column 1 of the first line, select all lines, hit Control + K, and remove the x. Formatting code just needs a non-whitespace character in column 1 to perform and indent by four spaces.

Answer 2

As far as style is concerned, I would recommend using something that makes maximum use of the Standard Library, e.g. the following code in C++11

template<class FwdIt, class Compare = std::less<typename std::iterator_traits<FwdIt>::value_type>>
void insertion_sort(FwdIt first, FwdIt last, Compare cmp = Compare())
{
 for (auto it = first; it != last; ++it) {
 auto const insertion = std::upper_bound(first, it, *it, cmp);
 std::rotate(insertion, it, std::next(it));
 }
}

Things to note compared to your own implementation:

• same signature as std::sort: two iterators and a comparison function object, this makes your algorithm usable with any container rather than just std::vector
• the comparison predicate used is std::less by default, but that can be changed by passing another function object or lambda expression: this makes your algorithm usable with more types and predicates
• use of standard algorithms
  • it repeatedly finds the insertion point of the next element pointed to by it using a binary search std::upper_bound in the currently sorted sub-range [first, it). Maybe for short input sequences, an ordinary std::find would give better cache locality (something to be tested).
  • it then inserts this element at the insertion point using the std::rotate algorithm
• the complexity is easy to reason about: an outer linear loop with an interior linear rotation, gives \$O(N^2)\$ complexity in the input range's length N == std::distance(first, last)

You could call it like this:

auto v = std::vector<int> { 4, 3, 2, 1 };
insertion_sort(begin(v), end(v)); // now 1, 2, 3, 4

Live Example.

Answer 3

• More whitespace here:

  for(int j=i-1; j>-1; j--)
  

  could help improve readability, especially when glancing at it:

  for (int j = i - 1; j > -1; j--)
  

• This line:

  else break;
  

  could use curly braces, at least to keep consistency:

  else
  {
   break;
  }
  

• For the loop counter type, use std::vector<int>::size_type instead of int, particularly with size(). You cannot guarantee that an int will be large enough, especially if you're sorting a lot of elements. It's also preferred to use std::size_type with a storage container since they all utilize this type.

  For brevity, you can use std::size_t instead, as std::size_type is usually just a typedef of it.