MOST SIMPLEST INSERTION SORT IMPLEMENTATION!

[advancedip]

Why does websites complicate insertion sort?

const int size = 10;
int arr[size] = {9,8,7,6,5,4,3,2,1,0};
for(int i = 1;i < size;i++)
	for(int j = 0; j < i;j++)
		if(arr[i] < arr[j])
			swap(arr[i], arr[j]);

[George P]

In modern C++ that code snippet will not compile. A regular array can't be initialized with a non-constant value.

[JLBorges]

Simple:

#include <algorithm>
#include <iterator>

template < typename ITERATOR > void isort( ITERATOR begin, ITERATOR end )
{
    // cppreference: "std::rotate is a common building block in many algorithms.
    //                This example demonstrates insertion sort"
    // https://en.cppreference.com/w/cpp/algorithm/rotate#Example
    for( ITERATOR iter = begin ; iter != end ; ++iter )
        std::rotate( std::upper_bound( begin, iter, *iter ), iter, std::next(iter) ) ;
}

template < typename SEQ > void isort( SEQ& seq )
{ isort( std::begin(seq), std::end(seq) ) ; }

http://coliru.stacked-crooked.com/a/5d96922c0046e40d

[lastchance]

void insertionSort( int A[], int n, int i = 1 )
{
   if ( i >= n ) return;
   rotate( upper_bound( A, A + i, A[i] ), A + i, A + i + 1 );
   insertionSort( A, n, i + 1 );
}

[jonnin]

Why does websites complicate insertion sort?

-- this is a constant problem with all kinds of code. You want a 5 line example of what you want to do. The web search gives you 4 pages of unrelated garbage.

There are 3 answers, I guess, and they overlap.
1) the author is showing off his 'skill'
2) the author is a wee bit nerdly and lacks the basic ability to state things in a simple manner. Think about your professors, and how they react to a yes or no question: most will give a dissertation.
3) the author is lazy, and the example is actually the same example for 20 different topics, and you have to dig out which one is relevant.

rarely, there is a #4 … the author is a noob, and you have stumbled across someone who isn't highly skilled but is trying to help out.

[Duthomhas]

@JLBorges
That is often touted as the C++ way to do an insertion sort, and is actually almost identical to what I first wrote as one, but while pretty it has significant performance problems.

An insertion sort is used for one thing only — pure, unadulterated speed for some N or fewer elements.

The most performant implementation in C or C++ will avoid everything but two loops and a comparison with an O(1) temporary. You can improve it by using std::move() to shift elements.

@advancedip
I have no idea how you consider that complicated.

Not the most readable, perhaps, but not bad. But definitely simple, especially in the realm of sorting algorithms. Bubble sort is harder to read, I my opinion.

Line 4 is wrong, by the way.

[George P]

This version of insertion sort is very common I find strewn throughout the interwebz:

void insertion_sort(int arr[], int length)
{
   int j, temp;

   for (int i = 0; i < length; i++)
   {
      j = i;

      while (j > 0 && arr[j] < arr[j - 1])
      {
         temp       = arr[j];
         arr[j]     = arr[j - 1];
         arr[j - 1] = temp;
         j--;
      }
   }
}

Whether this is simple or complicated, that is up for argument. This smells suspiciously of C. Using std::sort makes it a bit more C++ish.

[jonnin]

j-- should be moved up a line before arr[j-1]. microscopic, but hey :)

arr[j] = arr[--j]; // is this right? I forget the increment rules...
arr[j] = temp;

[George P]

You might be thinking of a java implementation:

void insertionSort(int[] arr) {
      int i, j, newValue;

      for (i = 1; i < arr.length; i++) {
            newValue = arr[i];

            j = i;

            while (j > 0 && arr[j - 1] > newValue) {
                  arr[j] = arr[j - 1];
                  j--;
            }
            arr[j] = newValue;
      }
}

The C++ implementation at http://www.algolist.net/Algorithms/Sorting/Insertion_sort is the same as what I posted from another site.

Another C++ variation:

void insertionSort(int arr[], int n)  
{  
    int i, key, j;  
    for (i = 1; i < n; i++) 
    {  
        key = arr[i];  
        j = i - 1;  
  
        /* Move elements of arr[0..i-1], that are  
        greater than key, to one position ahead  
        of their current position */
        while (j >= 0 && arr[j] > key) 
        {  
            arr[j + 1] = arr[j];  
            j = j - 1;  
        }  
        arr[j + 1] = key;  
    }  
}

[JLBorges]

I think a good tutorial on selection sort would not use code that demands O(1) random access to the sequence.
It is not an efficient sort for sequences that support random access. But all that it requires is multi-pass forward iteration; for example, it can be used to sort a linked list.