Thread: quicksort

  1. #1
    Registered User
    Join Date
    Dec 2006
    Posts
    3

    Thumbs up quicksort

    Hi, i've tried to get my quicksort to work, but i think because i have been looking at it for so long i cant see the problem with it so if someone can spot my mistake that would be great! it will run but it wont sort the array, i hve tried looking for code on the net but copuld not find any.

    Code:
    int parttition(int myArray[],int first, int last);
    void quicksort(int myArray[],int first, int last);  
    void quick( int size)
    {
    	
    int	*myArray; 	
    myArray = (int *) malloc (size * sizeof(int));	
    myArray= new int [size]; 
    int x;
    	srand((unsigned)time(0)); 
    	for (x=0;x<size;x++)	
    {		
              int random_integer = rand()/25; 		
              printf("%d\n",myArray[x]=random_integer);	
    }
    int first,last;
    	first=0;
    	last=size-1; 
    	quicksort( myArray, first,  last);
    	for (x=0;x<size;x++)
    	{
    		printf("%d\n",myArray[x]);	
                     }
    }
    
       int parttition(int myArray[],int first, int last)
    {
    	int pivot,i,s;
    	pivot=myArray[last];
    	i=first;
    	s=last-1;
    	int temp1=0,temp2=0,temp3=0; 
    	while( i<=last)	
                    { 
    		if (( myArray[i]>pivot))
    	{
    	temp1= myArray[i];		
    }	
    	i++;	
    }
    	while(s>=0)	
                     {
    		if ( myArray[s]<pivot)
    		{
    			temp2= myArray[s];
    		}
     		s--;
    	}
    		if ( s<i+1)
    		{
    			myArray[s]=temp1;
    			myArray[i-1]=temp2;  
     		}
    		else
    		{
    			return first;
    		}
    		temp3=pivot;
    		pivot=temp1;
    		myArray[i-1]=myArray[last];
    	} 
    
     void quicksort(int myArray[],int first, int last)
    {
     	int pivot=0;
    	if (first<last)
    	{
    	                pivot=parttition(myArray,first, last);			                 quicksort(myArray,first, pivot-1);
    			quicksort(myArray,pivot+1, last); 
    	}
    }

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    If you want somebody to look at your code, you should firstly indent it properly. It would also help if the program would be complete (with main, and includes). Something like that.
    Code:
    #include <cstdlib>
    #include <cstdio>
    #include <ctime>
    
    int parttition(int myArray[],int first, int last);
    void quicksort(int myArray[],int first, int last);  
    void quick( int size)
    {
        int	*myArray; 	
        myArray = (int *) malloc (size * sizeof(int));	
        myArray= new int [size]; 
        int x;
        srand((unsigned)time(0)); 
        for (x=0;x<size;x++)	
        {		
            int random_integer = rand()/25; 		
            printf("&#37;d\n",myArray[x]=random_integer);	
        }
        int first,last;
        first=0;
        last=size-1; 
        quicksort( myArray, first, last);
        for (x=0;x<size;x++)
        {
            printf("%d\n",myArray[x]);	
        }
    }
    
    int parttition(int myArray[],int first, int last)
    {
        int pivot,i,s;
        pivot=myArray[last];
        i=first;
        s=last-1;
        int temp1=0,temp2=0,temp3=0; 
        while( i<=last)	
        { 
            if (( myArray[i]>pivot))
            {
                temp1= myArray[i];		
            }	
            i++;	
        }
        while(s>=0)	
        {
            if ( myArray[s]<pivot)
            {
                temp2= myArray[s];
            }
            s--;
        }
        if ( s<i+1)
        {
            myArray[s]=temp1;
            myArray[i-1]=temp2;  
        }
        else
        {
            return first;
        }
        temp3=pivot;
        pivot=temp1;
        myArray[i-1]=myArray[last];
    } 
    
    void quicksort(int myArray[],int first, int last)
    {
        int pivot=0;
        if (first<last)
        {
            pivot=parttition(myArray,first, last);			                 
            quicksort(myArray,first, pivot-1);
            quicksort(myArray,pivot+1, last); 
        }
    }
    
    int main()
    {
        quick(10);
    }
    Now when I run this I get a runtime crash.

    When I turn on warnings, I get this for parttition: "Warning: control reaches end of non-void function" (you don't return anything).

    Not sure about the algorithm. Usually you determine a pivot value, then you start iterating from both ends and swap pairs of items where one is less than the pivot and the other is more than the pivot (in wrong order). Those two iterators should meet somewhere and the new partition would be at the meeting place (values in the first part are all smaller than values in the second part).
    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
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    It's hard to say, given that formatting, what anything is doing. My Hat of Guessing thinks you're using i in the while (s>=0) loop as meaningful, when it's leftover from the previous loop and will always equal last+1 (so it's not even in your array). But I might have missed a brace or whatever.

  4. #4
    Registered User
    Join Date
    Dec 2006
    Posts
    3
    one part i forgot to mention was that when i debug the program it carshes and tell me ther was a stack overflow and points to the partiotn function. but i have tried numerous things to solve the overflow but i cant figure out how to

  5. #5
    The larch
    Join Date
    May 2006
    Posts
    3,573
    The first big problem is that the pivot function doesn't return anything.

    Secondly the logic looks definately wrong. What your code apparently does:
    a) loop from start to end. The last value larger than pivot gets stored in a temporary.
    b) loop from end to start. The first value smaller than pivot gets stored in another temporary.
    c) Assign one temporary to array index -1 (s < 0 when the previous loop finishes) and the other towards the end.
    d) Do some random assignments and quit function without returning anything.

    I think you should start over with the partition function.
    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).

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Being one of the sorting exports on here I'd have to say that your "parttition" function doesn't partition. (oh and you spelt it wrong)

    The partitioning step of quicksort involves two loops nested within an outer loop:
    1. One inner loop searches forwards (initially from the start) searching for the first item that is less than the pivot.
    2. The other inner loop searched backwards (initially from the end) for the first item that is greater than the pivot.
    3. If you end up finding that your searches caught up to each other then you now exit the outer loop as there are no more items on the wrong side of the pivot.
    4. Or now that you have found two items that are both on the wrong sides of the pivot you swap them and continue with the outer loop.

    You don't have an outer loop!
    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"

  7. #7
    Registered User
    Join Date
    Dec 2006
    Posts
    3
    i'm still haveing problems with my partition function, i have changed it complelty but it is still not working, can any one help me please?
    Code:
    void parttition(int myArray[],int first, int last)
    {
    
    	int pivot,f,l;
    	pivot=myArray[last];
    	f=first;
    	l=last-1;int temp=0,temp1=0;
    	int x;bool state1=false,state2=false,state3=false;
    	while( f<l)
    	{
    
    		while((state1==false)&&(f<last))
    		{
    			if (myArray[f]>pivot)
    			{
    				f++;
    			}
    			else
    			{
    				state1=true;
    			}
    		}
    
    		while((state2==false)&&(l>first))
    		{
    			if (myArray[l]<pivot)
    			{
    				l--;
    			}
    			else
    			{
    				state2=true;
    			}
    		}
    		printf("\n%d\n",myArray[f]);
    		printf("%d\n",myArray[l]);
    		if (l<f)
    		{
    			temp=myArray[f];
    			myArray[f]=myArray[l];
    			myArray[l]=temp;
    			state3=true;
    			if ((myArray[f]>pivot)&&(state3==true))
    			{
    				temp1=myArray[f];
    				myArray[f]=myArray[last];
    				myArray[last]=temp1;	
    			}
    		}
    		else
    		{
    			if ((myArray[l]>pivot)&&(state3==true))
    			{
    				temp1=myArray[l];
    				myArray[l]=myArray[last];
    				myArray[last]=temp1;
    			}
    		}
    		printf("\n%d\n",myArray[f]);
    		printf("%d\n",myArray[l]);
    		int x;
    				printf("\n");
    		for (x=0;x<3;x++)
    		{
    			printf("%d\n",myArray[x]);
    		}	
    		parttition(myArray,first, l);
    		parttition(myArray,f, last);
    
    
    	}	
    
    
    }

  8. #8
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by WelshGrandSlam View Post
    Code:
    		while((state1==false)&&(f<last))
    		{
    			if (myArray[f]>pivot)
    This should be the other way 'round, shouldn't it? You want to skip ahead if your left array element is less than the pivot, and flag it for swapping if its greater. This way all the elements larger than the pivot end up on the right-hand side. (I realize upon looking back that iMalc disagrees with me, which worries me greatly.)

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Sorry you're right tabstop. I had it back-to-front, which would be for sorting descending. I need to work on my proof-reading.
    Sorry if I also put WelshGrandSlam wrong.
    It looks like you're doing the entire sort from the partition function now, since you're put the recursive calls in there. It's fine writing the whole thing as one function, but you can't really call it partition any more.
    Also you definitely shouldn't have the recursive calls inside the outer loop. It'll probably work but it will be far far slower than bubble sort.
    You're probably over-thinking it a bit too. My inner loops look like this:
    Code:
                do ++i; while (a[i] < tempItem);
                do --j; while (tempItem < a[j]);
    Last edited by iMalc; 01-23-2008 at 08:25 PM.
    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"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Scalability problems with Quicksort
    By hbejkosa in forum C++ Programming
    Replies: 3
    Last Post: 12-26-2008, 11:26 PM
  2. Question 39: Quicksort vs Linear Search
    By Kleid-0 in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 04-17-2005, 11:03 AM
  3. Using quicksort and radix sort for an anagram program
    By RazielX in forum C Programming
    Replies: 2
    Last Post: 05-03-2004, 09:33 AM
  4. quicksort problem
    By spinner in forum C Programming
    Replies: 9
    Last Post: 05-04-2003, 02:02 PM
  5. Quicksort
    By Nutshell in forum C Programming
    Replies: 1
    Last Post: 01-15-2002, 09:42 AM