what's wrong with this qsort code?

This is a discussion on what's wrong with this qsort code? within the C Programming forums, part of the General Programming Boards category; Hello everyone, my Prof. wrote a quicksort source code on the board. We have to implement it in another program. ...

  1. #1
    Registered User Sargnagel's Avatar
    Join Date
    Aug 2002
    Posts
    166

    Question what's wrong with this qsort code?

    Hello everyone,

    my Prof. wrote a quicksort source code on the board. We have to implement it in another program. The problem is, the quicksort function raises an exception. I've spent lots of hours to find the error but I still don't know what's wrong.
    I am nearly convinced that the Prof. made a mistake ...

    Anyway, here is the source code:
    Code:
    void quick(int array[], int l, int r)
    {
    	int cut;
    	
    	if(l < r)
    	{
    		cut = partition(array, l, r);
    		quick(array, l, cut);
    		quick(array, cut, r);
    	}
    }
    
    int partition(int array[], int l, int r)	
    {
    	int i, j, pivot, tmp;
    	
    	i = l-1;
    	j = r+1;
    	pivot = array[l];
    	
    	while(i < j)
    	{
    		while(array[++i] < pivot);
    		while(array[--j] > pivot);	
    											
    		if(i < j)							
    		{
    			tmp = array[i];
    	  		array[i] = array[j];
    	  		array[j] = tmp;
    	  	}
    	 }
    	 
    	 return j;
    }
    Thank you for your help.
    Last edited by Sargnagel; 01-12-2003 at 06:17 AM.

  2. #2
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,386
    A few remarks:

    > quick(array, l, cut);
    > quick(array, cut, r);

    Should be:

    quick(array, l, cut-1);
    quick(array, cut+1, r);

    In your prof's example code, the recursion will run forever, that is why you get that exception.

    And in the swap part of the partition function, I think this:

    >if(i < j)

    should be array[i] < array[j], because you want elements with value smaller or equal to pivot left of pivot and elements with value larger or equal to pivot right of pivot.

  3. #3
    Registered User Sargnagel's Avatar
    Join Date
    Aug 2002
    Posts
    166
    When I use this
    > quick(array, l, cut-1);
    > quick(array, cut+1, r);

    or this
    > quick(array, l, cut-1);
    > quick(array, cut, r);

    the array is sorted incorrectly. But when I use this
    > quick(array, l, cut);
    > quick(array, cut+1, r);

    the quicksort algorithm works.
    Thank you very much, Shiro!

    >if(i < j)

    should be array[i] < array[j], because you want elements with value smaller or equal to pivot left of pivot and elements with value larger or equal to pivot right of pivot.
    Hmmm ... I think this is already achieved with the following:
    while(array[++i] < pivot);
    while(array[--j] > pivot);

    array[i] is less than pivot and array[j] is greater than pivot and if ( i < j) the elements can be swapped.
    Last edited by Sargnagel; 01-12-2003 at 07:15 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. what is wrong in this simple code
    By vikingcarioca in forum C Programming
    Replies: 4
    Last Post: 04-23-2009, 08:10 AM
  2. Replies: 7
    Last Post: 08-06-2004, 10:14 AM
  3. what is wrong with this code please
    By korbitz in forum Windows Programming
    Replies: 3
    Last Post: 03-05-2004, 10:11 AM
  4. I cant find what is wrong with this code
    By senegene in forum C Programming
    Replies: 1
    Last Post: 11-12-2002, 06:32 PM
  5. Anyone see what is wrong with this code?
    By Wise1 in forum C Programming
    Replies: 2
    Last Post: 02-13-2002, 02:01 PM

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