Insertion sort–Recursive Method

Replacing loops with recursive requires functional knowledge of the code. In Insertion sort, we assume the first number as sorted and take the next subsequent number, compare with first number and move or swap it depending on the data structure.

Metaphor

     Another metaphor for insertion sort will be arranging the books based on their sizes. When you find a medium sized book, you insert it in the middle and reorder the full list to accommodate the middle book being inserted. This is what is done in a array kind of data structure. Even in linked list based insertion sort, we need to traverse the full sorted list to find the insertion point. But linked list way is easily visualized.

Concept

   Both iterative or recursive gives same performance. Recursive procedure blindly converts all the loops into recursive functions. Note that, in this recursive method, we will see a double-level recursion which is necessary in case of loop within a loop with different looping conditions.

Code

Some points:

• In recursive way, we take first( 0 )–> last (size –1) and take size-1 when it reaches condition first<last, that is last becomes 1 finally. In case of iteration, we do like 1 –> list size and assume arr[0] as sorted list. This means, recursive algorithm goes in a reverse way while normal loops go in a forward way.
• In the iterative version, there is a inner loop which shifts the elements to get a whole to insert the element in the sorted list. In recursive version, this is taken care by insertInOrder function.
• Note that, insertInOrder function has 3 operations
• Check whether the element is less than the last element in the sorted list. Then just append the element to the sorted list by doing,  a[last+1] =element
• if on a recursion to shift elements, reaches the end (that is, first < last). Then start returning. Note that, if element >= a[last] will occur on every call and only when it becomes false, recursion comes up. In each recursion, there are in turn 2 checks
• element > a[last]
• element < a[last]
• When the element<a[last] in a recursive function return, we will have the correct index in the last variable. We just put the element at that position and shift. Note that, shifts inside the array happens always except when element >= a[last]!!

   1:  void insertInOrder( int element,int *a, int first, int last)

   2:  {

   3:      if (element >= a[last])

   4:          a[last+1] = element;

   5:      else if (first < last)

   6:      {

   7:          a[last+1] = a[last];

   8:          insertInOrder(element, a, first, last-1);

   9:      }

  10:      else // first == last and element < a[last]

  11:      {

  12:          a[last+1] = a[last];

  13:          a[last] = element;

  14:      }

  15:  }

  16:   

  17:   

  18:  void insertion_sort_recur(int *arr, int first, int last)

  19:  {

  20:      if(first < last)

  21:      {

  22:          insertion_sort_recur(arr, first, last-1); // avoids looping thru arr[0..last-1]

  23:          insertInOrder(arr[last], arr, first, last-1); // considers arr[last] as the first element in the unsorted list

  24:      }

  25:  }

  26:   

  27:  void main()

  28:  {

  29:      int A[]={5,3,2,4,6,1};

  30:      insertion_sort_recur(A,0,5);

  31:  }

 

Important points

• By seeing the above code, it looks clear that, there is direct conversion of iterative procedure to a recursive one. But note that, when you make some function recursive, there should be a recursion end condition along with other conditions.
• If the iterative version of the algorithm is nested, then the recursive usually looks like the above code.
• The above code is taken from: http://www.cs.siu.edu/~mengxia/Courses%20PPT/220/Chapter11.ppt
• This is an exercise problem in “Introduction to Algorithm, Corman-Lewis” book.