# Thread: Can someone help me with a Recusive Insertion Sort problem

1. ## Can someone help me with a Recusive Insertion Sort problem

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";
}```

2. I would assume that you make it recursive by turning the outer loop into recursion. I don't see why you would need a different signature for that. (Of course, in case of this algorithm there doesn't seem to be any benefit from using recusion.)

You should also check your array bounds or consider the C++ convention that the end marker does not itself belong to the range.

Code:
```for (int j = first+1 ; j <=last ; ++j){
int kti = a[j];```

3. Try to imagine that you're already part-way performing the recursive insertion sort. I.e. You have an array with some items in the lower part of the array that are sorted, and some items in the upper part of the array that are not. You have an index of the first non-sorted item in the array and you have a count of how many items are in the array. Those are your 3 parameters. (The iterative version only needs two as 'first' is always zero)

Now the task of your recursive insertion sort is to either:
Insert the first item from the unsorted portion into the sorted portion, or...
If there are no more unsorted items - stop.
Then to make the recursive call passng it the array, the index of the first unsorted item (which has changed now), and the number of items.

That should make it pretty easy.

4. okay thanks for the help.. I think im almost there. However I have hit a snag.
Here is my altered code of the final function, Im pretty sure this should work!!!!

Code:
```	void insSortRec (int b[], int len){
int j,k,temp;
if (len > 0){
insSortRec (b, len-1);
temp = b[len-1];
k = len-2;
while ((temp < b[k]) && (k >=0)) k = k-1;
j=k+1;
for (k=len-1; k>j; k--){
b[k] = b[k-1];
b[j] = temp;
}
printArray(b,N);
}
cout << "\n";
}```
however it dosnt work from what I can tell its having issues with some of the numbers in the array.

This is the output of the function

26 5 26 1 61 11 59 15 11 19
5 26 26 1 61 11 59 15 11 19
5 26 26 1 61 11 59 15 11 19
1 1 26 26 61 11 59 15 11 19
1 1 26 26 61 11 59 15 11 19
1 1 11 11 26 61 59 15 11 19
1 1 11 11 26 59 61 15 11 19
1 1 11 11 15 15 59 61 11 19
1 1 11 11 11 11 15 59 61 19
1 1 11 11 11 11 15 19 19 61
But this is what it should look like

5 26 26 1 61 11 59 15 11 19
5 26 26 1 61 11 59 15 11 19
1 5 26 26 61 11 59 15 11 19
1 5 26 26 61 11 59 15 11 19
1 5 11 26 26 61 59 15 11 19
1 5 11 26 26 59 61 15 11 19
1 5 11 15 26 26 59 61 11 19
1 5 11 11 15 26 26 59 61 19
1 5 11 11 15 19 26 26 59 61
XD my brain is putty.

5. I see you've gotten it down to two parameters by performing the recursive call first. I must admit I hadn't considered doing that. It simplifies things slightly, but you wont bennefit from any possible tail-recursion elimination that the compiler might otherwise have performed.

It looks like the problem is that you need to move this line out of the loop:
Code:
`				b[j] = temp;`
The loop is only to move items over. You put the item in the newly created hole after that.

Also, in your while loop, reverse the order of the ANDed conditions. You need to be sure that k >= 0 before you use k for array indexing or you'll go off the start of the array potentially causing a crash.

Nice job.

6. GAA! lol now thats it!!!! it works, it makes sense now! I just didn't see that,
the first 800 times i ran through it in my head! couldn't understand why it didn't want
to work!

Thanks for the help guys! seriously these boards are so much help! Im only new to c++
have moderate ability in C but taking some c++ papers this semester for my degree and finding the teachers in both my papers are somewhat unorganized.. If it wasn't for c++boards i would be up the creek!

Thanks again!
KC

Popular pages Recent additions