Recursive functions using pointers

kai85 · #1 02-Aug-2005, 09:26

hi ,
im writing this(recursive) code for the quick sort algorithm and I'm using pointers as the function parameters.
but the problem Im having is that the swap function which i call just won't change the variables places in the global array I've declared.

I'm using refrenced parameters in this swap function , and i have no idea why it won't change their places.
here's the code:

CPP / C++ / C Code:


#include <iostream.h>


void quicksort(int array[], int size,int start,int end);
int partition(int array[],int size,int *startptr, int *sptr);

void swap(int &a,int &b);
int array[10]={45,3,7,5,14,23,17,43,2,1};
	
int main()
{
	cout<<"the unsorted array is:"<<endl;
	
	for(int i=0;i<10;i++)
		cout<<array[i]<<" ";
	cout<<endl;
   	
	quicksort(array,10,array[0],array[9]); 

	cout<<"the sorted array is:"<<endl;
	
	for(int i=0;i<10;i++)
		cout<<array[i]<<" ";
	cout<<endl;
 
	return 0;
}


void quicksort(int array[], int size,int start,int end){

	int k;
	if (size==1)
		return;
	else
	k=partition(array,size, &start,&end);
	quicksort(array,k,start,k-1);
    quicksort(array,size-k-1,k+1,end);
}


int partition(int array[],int size,int *startptr, int *sptr)
{
	
	int index1=0,index2=0;
	int j=-1;
	int i=0 ;

	while(*startptr != *sptr ){//if the values aren't equal 
// compare them,and swap their places 
 //if needed, else that certain variable's 
 //place has been found,return it's index.
		

                      if (j* (*startptr) < j* (*sptr)){
		
			swap(*startptr,*sptr);//this function is not ... functioning    
                                                      // properly
			
			if(j==-1)
				index1=index1+i+1;
			else
				index2=index2+i+1;
            
                        sptr=startptr;//change the pointers places too.
//startptr is supposed to always point to 
//the variabel which we want to find it's index.
		    
			
			
			if(j<0)
				startptr=&array[size-index1];
			else
			    startptr=&array[index2];
				j=j *(-1);
				i=-1;
		}
	
   	  
        sptr=sptr+j	;
		i++;
	}
		if(j==-1)
		return size-index1;
    	else
			return index2;
}



void swap(int &a,int &b)
{
	int temp;
	temp=a;
	a=b;
	b=temp;
}

what's wronge with it?
thanks in advance

davekw7x · #2 02-Aug-2005, 13:53

Quote:

Originally Posted by kai85

hi ,
im writing this(recursive) code for the quick sort algorithm
what's wronge with it?
thanks in advance

When I have a function that I suspect is not working, I make a test program that just calls that function and does nothing else except print the results:

CPP / C++ / C Code:

#include <iostream>

using namespace std;


void swap(int &a,int &b);

int main()
{
  int x = 1;
  int y = 2;
  int *v = &x;
  int *w = &y;
  printf("Initially           x = %d, y = %d, *v = %d, *w = %d\n\n", 
          x, y, *v, *w);

  swap(x, y);
  printf("After swap(x, y)    x = %d, y = %d, *v = %d, *w = %d\n\n", 
          x, y, *v, *w);

  swap(*v, *w);
  printf("After swap(*v, *w)  x = %d, y = %d, *v = %d, *w = %d\n\n", 
          x, y, *v, *w);

  return 0;
}

void swap(int &a, int &b)
{
  int temp;
  temp = a;
  a = b;
  b = temp;
}

My output:

Code:

Initially           x = 1, y = 2, *v = 1, *w = 2

After swap(x, y)    x = 2, y = 1, *v = 2, *w = 1

After swap(*v, *w)  x = 1, y = 2, *v = 1, *w = 2

So the function does seem to work.

Now as to your program: what made you think that the problem was the swap() function?

When I tried your program it gave this:

Code:

the unsorted array is:
45 3 7 5 14 23 17 43 2 1

It never printed the sorted array. What could have happened?

Well, here's how I start to debug things like this:

First of all, I usually put print statements around function calls (especially recursive ones):

in main:

CPP / C++ / C Code:

...
...
  cout << "calling quicksort" << endl;
  quicksort(array,10,array[0],array[9]); 
  cout << "after quicksort" << endl;
...
...

Now the output that I get is this:

Code:

the unsorted array is:
45 3 7 5 14 23 17 43 2 1
calling quicksort

So, as I suspected, it's never returning back to main() from quicksort(). (The function probably calls itself and calls itself and calls itself ... until the program runs out of stack space to hold return addresses, then the program unceremoniously quits --- no message or anything, just returns.)

Now,to check this, I made a global variable named counter and initialized it to zero:

CPP / C++ / C Code:


int counter = 0;
int main()
{
...
...

Then, in quicksort(), I put this at the beginning:

CPP / C++ / C Code:

void quicksort(int array[], int size,int start,int end){

  int k;

  cout << "In quicksort: counter = " << ++counter 
       << ", size = " << size 
       << ", start = " << start 
       << ", end = " << end << endl;
...
...

Try it and see what it tells you. (Ctrl-C makes the madness stop.) If you want to "single-step" through the infinite loop, you can put cin.get() after the cout statement. Now it stops each time and waits for you to press "Enter" before continuing. Look at the first few times then hit Ctrl-C to exit.

If you need to drill down into lower functions, put printout statements as each one is called, etc. The idea is to make the program tell you exactly what it is doing, then you should be make it do the right thing.

Regards,

Dave

CMan · #3 02-Aug-2005, 14:49

your swap function is fine but the arguments you're passing are not. I'm not sure what the problem is but try passing "start" and "end" by reference instead pointer like this

Code:

...
partition(array, size, start, end);
...
int partition(int array[],int size,int &startptr, int &sptr)
{...

Hope this helps

kai85 · #4 02-Aug-2005, 15:06

hi,

i'm compiling with vc++ , and i started debugging line to line , i mean by using F10 and F11, after the swap function was called, the variables in the array weren't changed in the output window(they were changed inside the swap function but the array stayed the same)
.so this is how i (think )i know thats where the problem occurs... so i wrote a similar program , just like the one u wrote above ,but that answered , and i though maybe it's somthing i don't know , the pointers are pointing to the correct places , and the swap function does seem to be swaping the variables , but the array stays the same . it seems to be constant .
but i'll go try what u said ,(both of u) and see what happens.
thanks again.

WaltP · #5 02-Aug-2005, 16:53

Quote:

Originally Posted by kai85

hi,

i'm compiling with vc++ , and i started debugging line to line , i mean by using F10 and F11, after the swap function was called, the variables in the array weren't changed in the output window(they were changed inside the swap function but the array stayed the same)
.so this is how i (think )i know thats where the problem occurs... so i wrote a similar program , just like the one u wrote above ,but that answered , and i though maybe it's somthing i don't know , the pointers are pointing to the correct places , and the swap function does seem to be swaping the variables , but the array stays the same . it seems to be constant .
but i'll go try what u said ,(both of u) and see what happens.
thanks again.

All you are doing is swapping the temporary pointers, not the values. Try:

CPP / C++ / C Code:

void swap(int &a,int &b)
{
  int temp;
  temp=*a;
  *a=*b;
  *b=temp;
}

Now the values the pointers point to are swapped.

davekw7x · #6 02-Aug-2005, 17:06

Quote:

Originally Posted by WaltP

All you are doing is swapping the temporary pointers, not the values. Try:

CPP / C++ / C Code:

void swap(int &a,int &b)
{
  int temp;
  temp=*a;
  *a=*b;
  *b=temp;
}

Now the values the pointers point to are swapped.

No. He is passing by reference (a and b are ints, not pointers). I personally would have used pointers as arguments, but I didn't want to impose my sense of style on his, since I didn't want to make him change his program only to find that it had no bearing on his problem.

Your snippet won't compile in any standard C++ compiler, since it is trying to de-reference the un-de-referenceble. (And C compilers generally don't allow pass-by-reference, so they wouldn't even begin to compile it.)

My previous example, changed so that swap uses pointers, becomes the following: (I wouldn't normally dream of second-guessing anyone, but this time I am guessing that this is kind of what you had in mind.)

CPP / C++ / C Code:

#include <iostream>

using namespace std;


void swap(int *a,int *b);

int main()
{
  int x = 1;
  int y = 2;
  int *v = &x;
  int *w = &y;
  printf("Initially           x = %d, y = %d, *v = %d, *w = %d\n\n", 
          x, y, *v, *w);

  swap(&x, &y);
  printf("After swap(&x, &y)  x = %d, y = %d, *v = %d, *w = %d\n\n", 
          x, y, *v, *w);

  swap(v, w);
  printf("After swap(v, w)    x = %d, y = %d, *v = %d, *w = %d\n\n", 
          x, y, *v, *w);

  return 0;
}
void swap(int *a,int *b)
{
  int temp;
  temp = *a;
  *a = *b;
  *b = temp;
}

The output:

Code:

Initially           x = 1, y = 2, *v = 1, *w = 2

After swap(&x, &y)  x = 2, y = 1, *v = 2, *w = 1

After swap(v, w)    x = 1, y = 2, *v = 1, *w = 2

So one way works as well as the other.

Regards,

Dave

(Both Stroustrup and I believe that gratuituous use of pass-by-reference can be hazardous to your mental health. Just because you can pass by reference doesn't mean that you should pass by reference. It's not "wrong", however.)

WaltP · #7 02-Aug-2005, 18:52

Quote:

Originally Posted by davekw7x

No. He is passing by reference (a and b are ints, not pointers). I personally would have used pointers as arguments, but I didn't want to impose my sense of style on his, since I didn't want to make him change his program only to find that it had no bearing on his problem.

Oh. Sorry about that. I didn't look close enough. I saw the & and my mind went to *.

alcedo · #8 03-Aug-2005, 03:55

la la, to sum things up:

CPP / C++ / C Code:

void swap(int &a,int &b)  //if u are getting address of a

swap(x, y);                // u dont have have do declare *x

void swap(int *a, int *b)  //if u declare as such

swap(&x, &y)               //than u just have to do this. just be consistent.

LuciWiz · #9 03-Aug-2005, 05:05

Quote:

Originally Posted by davekw7x

Both Stroustrup and I believe that gratuituous use of pass-by-reference can be hazardous to your mental health. Just because you can pass by reference doesn't mean that you should pass by reference. It's not "wrong", however.

Not everyone agrees.
But I appreciate most the people who can accept another point of view - like you and Mr. Stroustrup. I'm not decided on this issue myself, but I don't like reading the self-righteous opinions I found all over the Internet - "my way is the way".

Best regards,
Lucian

kai85 · #10 03-Aug-2005, 07:29

Quote:

Originally Posted by alcedo

la la, to sum things up:

CPP / C++ / C Code:

void swap(int &a,int &b)  //if u are getting address of a

swap(x, y);                // u dont have have do declare *x

void swap(int *a, int *b)  //if u declare as such

swap(&x, &y)               //than u just have to do this. just be consistent.

I have no idea what u mean, I havn't declared anything , I'm just saying swap the "variables" the pointers are pointing to, derefrence the pointer .
if i say:
cout<<*startptr<<endl;
what would that mean?what would it see out?
that is definetly not the problem,what u've said is too basic., and as i said i already wrote another program testing to see if it actually swapped them , and it did.
ANYWAY, I think I'm gonna have to work on it a bit more.

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
help in c++ recursive functions	vinch	C++ Forum	7	04-Jan-2006 13:22
Endless recursive function	teflon	C++ Forum	3	26-Jul-2005 12:31
Major problem with recursive function, help..	kakamuti	C Programming Language	4	19-Dec-2004 08:47
Understanding Recursive Functions	Nexa	C++ Forum	5	19-Nov-2004 12:51
recursive algorithm	vienne	C Programming Language	2	21-Jul-2004 12:54