Hello there, before you say it I know, pointless!

I have been asked to write two insertion sort functions.

One that uses Iteration and another that uses Recursion, At first I had no problems writing the function in its iterative form, as you can see if you compile the code.

However Im having difficulty trying to write the recursive function.. I just cannot get my head around the function as a whole. I understand I have to call the function in itself.. but from there I kinda get lost.

I have been working on this for the past few days, I have asked the tutor for help however when he explained it to me I thought i had it.. once I got home however and went to write it.. I made a mess of it and im completely lost once again!

here is my code, if there is anyone that can point me in the right direction or maybe show me how to do this with pseudo code that would be greatly appreciated! I want to learn how to do this.. so I know for myself!!!!

the problem function is at the bottom of the code

Code://////////////////////////////////////////////////////////////////////////////// // // Author: // name: #######, ID Number: ####### // Year: 2008, Course: ####### // // Program Name: // Description: // //////////////////////////////////////////////////////////////////////////////// #include <iostream> using namespace std; //constant size N used on arrays const int N = 10; //Prints author details void detials (void); /*printArray prints the values of the array sorted by ether the insSortItr fuction or the insSortRec function*/ void printArray (int dat[], int n); /*insSorItr sorts data in ascending order of the array [a[first]...[last]] using itteration (while and for loops).*/ void insSortItr (int a[], int first, int last); /*insSortRec sorts data in ascending order of the array [a[first]...[last]]using recursion.*/ void insSortRec (int b[], int c[], int index, int len); int main (){ // array of numbers to sort for the insSortItr function int dataA[N] = {26,5,26,1,61,11,59,15,11,19}; /* array of unsorted numbers that insSortRec function will read and sort into final array */ int dataB[N] = {26,5,26,1,61,11,59,15,11,19}; /*final will be the final sorted array of numbers from dataB unsortted array, they will be sorted by the recursive insSortRec insertion sort function and stored*/ int final[N]; /*final will be the final sorted array of numbers from dataB unsortted array, they will be sorted by the recursive insSortRec insertion sort function and stored*/ detials (); insSortItr (dataA,0,N); cout << "After iterative insertion sort finished:\n"; printArray (dataA,N); cout << "\n\n"; cout << "Part B: Initial array:\n"; printArray (dataB,N); cout << "\n\n"; insSortRec (final,dataB,0,N); //cout << "After recursive insertion sort finished:\n"; //printArray (final,N); //end - clearscreen } ////////////////////////////////////////////////////////////////////// //////////////// voids functions ////////////////////////////////////////////////////////////////////// //A fuction that displaying all Author names and Ids void detials(void){ cout << "159.201 Assingment 1\n"; cout << "Smith C, ID:07199104\n\n"; } /* PrintArray function prints the array values supplied to it when calling it at any time*/ void printArray (int dat[], int n){ for (int k = 0; k < n; ++k){ cout << dat[k] << " "; } } /*iterative insertion sort - insSortItr takes array input value iterates through the loop preforming insertion sort algorithum and printing values out at each itteration using the printArray function*/ void insSortItr (int a[], int first, int last){ cout << "Part A: Initial array:\n"; printArray(a,last); cout << "\n\n"; for (int j = first+1 ; j <=last ; ++j){ int kti = a[j]; int i = j-1; //cout << a[1] << "\n"; while (i >= first && a[i] > kti){ a[i+1] = a[i]; i = i-1; a[i+1] = kti; } printArray(a,last); // displays content of a each iteration cout << "\n"; } cout << "\n"; } //recursive insertion sort - insSortRec //display all intermediate results void insSortRec (int b[], int c[], int index, int len){ int temp = c[index]; /* need to figure out how to insert contence in temp into the final array then display it like insSortItr*/ if(index < len -1){ index++; insSortRec(b,c,index,len); // This is the recursive part } //printArray (c,N); //cout << "\n"; }