Can someone help me with a Recusive Insertion Sort problem

This is a discussion on Can someone help me with a Recusive Insertion Sort problem within the C++ Programming forums, part of the General Programming Boards category; Hello there, before you say it I know, pointless! I have been asked to write two insertion sort functions. One ...

  1. #1
    Registered User
    Join Date
    Oct 2007
    Posts
    51

    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. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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];
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,295
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Oct 2007
    Posts
    51
    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. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,295
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User
    Join Date
    Oct 2007
    Posts
    51
    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 subscribe to a feed

Similar Threads

  1. problem with gets and bubble sort
    By wwwildbill in forum C Programming
    Replies: 4
    Last Post: 04-04-2009, 01:31 AM
  2. Compile problem: sort() cannot be used as a function!?
    By ac251404 in forum C++ Programming
    Replies: 2
    Last Post: 06-01-2006, 12:58 PM
  3. Shell Sort with Vectors Problem
    By TheSpoiledMilk in forum C++ Programming
    Replies: 4
    Last Post: 11-22-2005, 02:05 PM
  4. Replies: 5
    Last Post: 11-07-2005, 10:34 PM
  5. netonotisr inor (insertion sort)
    By The Brain in forum C++ Programming
    Replies: 0
    Last Post: 05-04-2005, 03:11 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21