How can I convert iterative insertion sort to a recursive insertion sort.

[alyuleth]

I've been trying to convert this iterative insertionsort to recursive but am having trouble. Here's the Original:

      void insertionSort()
    {
        X temp;
        int j;
        for(int i=1;i<3;i++)
        {
            temp=array[i]; 
            j=i-1;
            while(temp<array[j])
            {
                array[j+1]=array[j];
                j--;
            }
            array[j+1]=temp;
        }
    }

Here's the new version I am trying to write. I get an output where the first element in my array is repeated twice.

   void sort()
    {
        X temp;
        int j ;
        int i = 1;
        temp = array[i];
        j=i-1;
        while(j>0 && temp>array[j-1])
        {
            array[j]=array[j-1];
            j--;
        }
        array[j] = temp;
        if (i + 1 <= j)
        {
            sort();
            i++;
        }
    }

[salem c]

Well it would help if your sort function had parameters, instead of messing with global variables.

You need to be able to pass some kind of context (like the bit of the sub-array to be sorted) from one call to another.

void sort ( int *array, int fromIndex, int toIndex );

[alyuleth]

I'm trying to write it based on a template array class where array is a T pointer and I was having trouble with various parameters and I was trying to simplify it. Though that might have made it harder for me...
This is what main looks like:

  const int SORT_MAX_SIZE = 32;
    // instantiate test object of class Array<double> with size 32
    Array<double>test(SORT_MAX_SIZE);
   //setting element values
    //n is position and val is the value to be inserted into array
    //doubles
    test.setArray(0, 0.6);
    test.setArray(1, 0.1);
    test.setArray(2, 0.3);
    test.getArray();
    //test.insertionSortRecur();
    test.sort();
    test.getArray();

[salem c]

Well that wasn't obvious at all from your first post.

Sure, your public interface can be void, but internally, you need parameters.

class Array {
  private:
    int arrlen;   // would end up being 3 from your current main, via setArray() calls
    void insertionSortRecursive(int start, int end);
  public:
    sort() {
        insertionSortRecursive(0,arrlen);
    }
}

[Duthomhas]

First thing to note: your array is only four elements long. What happens when your professor asks you to make it 20?
— Do something to replace that 3 on line 5 with a member variable in the class.


Your original code has a buffer overflow on line 9. You seem to have noticed and corrected in the next code, but you are missing the point of recursion.

With iterative stuff, we use a loop and variables to control that loop.

void print_iterative( const char* s )
{
  int n = 0;     // our control variable
  while (s[n])   // our don't-exit condition (only quit when s[n] is zero)
  {
    cout << s[n];  // do stuff
    n++;         // update our control variable
  }              // next loop
}

To make it recursive, we replace the loop with a function call, and all the variables that control it become arguments to the function.

void print_recursive( const char* s, int n )  // the control variable is now an argument
{
  if (!s[n]) then return;  // the exit condition (negated from the iterative version above)
  cout << s[n];            // do stuff
  print_recursive( s, n + 1 );  // update our control variable and next loop
}

It’s All About The Loops
An insertion sort works over TWO loops^[1]. Given an array of elements indexed [0..N-1] (where N is the number of elements in the array):

    • The outer loop is from 1 to N-1, accessing the next element to insert into the sorted sequence.
    • The inner loop is to rotate^[2] a portion of the array rightward, from the index where
      the element needs inserting to where the element is now.

You can perform recursion on either (or both) of these loops. Take one problem at a time.


Next Element To Insert Loop
Iteratively, that's just:

void sort()
{
  for (int i = 1; i < N; i++)
  {
    // next element to insert is: array[i]
  }
}

The control variable is i, so that should be an argument to your function. (You have the array and N variables as part of your class, right?)

void sort_body( int i )
{
  if (!(i < N)) then return;

  // next element to insert is: array[i]

  sort_body( i + 1 );
}

Now the sort() function becomes just:

void sort()
{
  sort_body( 0 );
}

Rotate
Here is the iterative part:

  X temp = array[i];

  int j = i - 1;
  while ((j > 0) and (array[j] > array[i]))  // don't-exit conditions
  {
    array[j+1] = array[j];  // do stuff
    j--;  // update our control variable
  }

  array[j] = temp;

Dang, that looks quite a bit more complex. Our goal should be to make it as simple as possible.

The first thing we are going to do is NOT mix it up with the other recursion — we will split it off into yet another function.

void sort_body( int i )
{
  if (!(i < N)) then return;

  sort_rotate( i );

  sort_body( i + 1 );
}

Hmm, that part does look much nicer, but now we need to consider what to do with temp. That part is outside the loop, so it should be outside the loop as well:

void sort_body( int i )
{
  if (!(i < N)) then return;

  X temp = array[i];
  sort_rotate( i );
  array[ ? ] = temp;  // fooey, a problem.

  sort_body( i + 1 );
}

The problem is easily solved though. Stop reading a moment and see if you can think any potential solutions.

So, here are two:

    • Return the j index to sort().
    • Give sort_rotate() the value so that sort() doesn’t have to care.

The first solution would look like this:

  X temp = array[i];
  array[ sort_rotate( i ) ] = temp;

BTW, do not combine those lines, as the compiler’s optimizer will not play nice with the side effects.

The second solution would look like this:

  sort_rotate( i, array[i] );

Notice the missing temp variable?

It has moved to a convenient argument of the sort_rotate() function, which sort_rotate() can use before returning (because it found the insertion place or the beginning of the array — the exit conditions).

...

At this point I could write the final solution for you.
But I’m not gonna (at least not for a week or two.)

You have enough here to write a sort_rotate() function that will take the place of the j loop. Do your best, and see how far you get. If you get stuck again, post your current solution (in a new post, please don’t edit your first post), and we’ll help.


[1]
A very simplistic insertion sort can use three loops, but if you, dear reader, have used an additional loop just to find the place to insert, try to figure out how to combine it with the rotate/shift loop.

[2]
A rotate is like a shift, except that stuff that would be shifted off one end gets stuck on the other. For example:

    { 4, 3, 2, 1 }     // original array
    { 1, 4, 3, 2 }     // rotated right by one element

You can also see how this is useful in an insertion sort: the item on the right end of the sequence is rotated to the left end, causing everything to shift right one.

This rotation is the core of an insertion sort.

[edits] Stupid BBCode formatting grief...

[Duthomhas]

Did you settle with that half-a** answer you got at Cprogramming.com?

Or not? Did you get anywhere?

[Duthomhas]

Well, it has been 6 days, and no further response.
I said I’d post a final solution, so here it is:

//-----------------------------------------------------------------------------
// Stable Recursive Insertion Sort

#include <ciso646>

template <typename T>
void insertion_sort_rotate( T* xs, int n, T x )
{
  if ((n < 0) or (xs[n] <= x))
  {
    xs[n+1] = x;
  }
  else
  {
    xs[n+1] = xs[n];
    insertion_sort_rotate( xs, n - 1, x );
  }
}

template <typename T>
void insertion_sort_next( T* xs, int n, int N )
{
  if (n >= N) return;
  insertion_sort_rotate( xs, n - 1, xs[n] );
  insertion_sort_next( xs, n + 1, N );
}

template <typename T>
void insertion_sort( T* xs, int N )
{
  insertion_sort_next( xs, 1, N );
}

And a test program:

//-----------------------------------------------------------------------------
// Example Using Stable Recursive Insertion Sort
//
#include <algorithm>
#include <iostream>
#include <iterator>
#include <sstream>
#include <string>
#include <vector>

#ifdef _WIN32
  #include <io.h>
  #define isatty _isatty
#else
  #include <unistd.h>
#endif

int main( int argc, char** argv )
try
{
  std::vector <double> xs;
  if (isatty( 0 )) std::cout << "xs? ";
  {
    std::string s;
    getline( std::cin, s );
    std::istringstream ss( s );
    std::copy( 
      std::istream_iterator <double> ( ss ), 
      std::istream_iterator <double> (),
      std::back_inserter( xs ) );
  }

  insertion_sort( xs.data(), xs.size() );

  for (auto x : xs) std::cout << x << " ";
  std::cout << "\n";
}
catch (...)
{
  std::cerr << "xs must be a list of numbers separated by spaces!\n";
  return 1;
}

Example runs

C:\Users\Michael\Programming\cpp\foo> clang++ a.cpp -std=c++14

C:\Users\Michael\Programming\cpp\foo> a
xs? 5 4 3 2 1
1 2 3 4 5

C:\Users\Michael\Programming\cpp\foo> echo 9 7 5 3 1 2 4 6 8 0 |a
0 1 2 3 4 5 6 7 8 9

C:\Users\Michael\Programming\cpp\foo> _

It isn’t as horribly inefficient as it looks. The only real overhead is the function calls — which, if properly optimized into tail call recursion, should be minimal.

Of course, a simple iterative version will still beat the pants off of this. But I don’t think you’ll notice until you are sorting a thousand elements or so. (I haven’t profiled!)

Remember, insertion sort is designed for speed at N < 100*.

*Or roundabouts.

Build yourself a quicksort that optimizes on the insertion sort, and swap out to the recursive version and time the sorting of 2000 elements and you’ll see the difference. (I think that’ll be enough to see the difference without the timer.)

Anyway...