Thread: qsort

  1. #1
    eat my shorts!
    Join Date
    Apr 2002
    Posts
    294

    qsort

    hey,

    i am having problems with partition:
    Code:
    int Partition(int* panNumbers, int nSize)
    {
    
    	
    	int nPivot = panNumbers[0];
    	int nLeftIndex = 0;
    	int nRightIndex = nSize;
    	while (nLeftIndex < nRightIndex)
    	{
    		while (panNumbers[nLeftIndex] <= nPivot)
    			nLeftIndex++;
    	
    		while (nRightIndex > nLeftIndex)
    			while (panNumbers[nRightIndex] >= nPivot)
    				nRightIndex--;
    	
    
    			if (nLeftIndex < nRightIndex)
    		{	
    			int temp = panNumbers[nLeftIndex];
    			panNumbers[nLeftIndex] = panNumbers[nRightIndex];
    			panNumbers[nRightIndex] = temp;
    		}
    	}
    return nRightIndex;
    }
    i have been looking at some examples but cant seem to figure it out...
    Games Reviews Previews Desktop Themes Downloads Paintball Forums Shareware Freeware and much more

    The best in Technology and Gaming News

    www.back2games.com

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    That's a lot of loops for a simple partition algorithm. Try something along these lines and call me in the morning:
    Code:
    int partition ( int a[], int low, int high )
    {
      int pivot;
      int i, prev;
    
      swap ( a[low], a[( low + high ) / 2] );
    
      pivot = a[low];
      prev = low;
    
      for ( i = low + 1; i <= high; i++ ) {
        if ( a[i] < pivot )
          swap ( a[++prev], a[i] );
      }
    
      swap ( a[low], a[prev] );
    
      return prev;
    }
    
    void quicksort ( int a[], int low, int high )
    {
      int pivot;
    
      if ( low >= high )
        return;
    
      pivot = partition ( a, low, high );
    
      quicksort ( a, low, pivot - 1 );
      quicksort ( a, pivot + 1, high );
    }
    My best code is written with the delete key.

  3. #3
    Registered User
    Join Date
    Aug 2003
    Posts
    470
    I have not tested this, but I think this is what you want:
    Code:
    int Partition(int* panNumbers, int nSize)
    {
        int nPivot = panNumbers[0];
        int nLeftIndex = 0;
        int nRightIndex = nSize;
       
       while (nLeftIndex < nRightIndex)
       {
              while (panNumbers[nLeftIndex] <= nPivot)
                    nLeftIndex++;
              
              while(panNumbers[nRightIndex] > nPivot)
                    nRightIndex--;
    
              //  panNumbers[nLeftIndex] > nPivot and panNumbers[nRightIndex] <= nPivot
              //  Because of this condition we may safely swap
    
              swap(panNumbers[nLeftIndex], panNumbers[nRightIndex]);
         }
    
         return nRightIndex;      
    }

  4. #4
    Registered User
    Join Date
    Aug 2003
    Posts
    470
    The assignment nRightIndex = nSize is probably wrong, depending on the meaning of the nSize parameter.

  5. #5
    eat my shorts!
    Join Date
    Apr 2002
    Posts
    294
    nSize is the size of the array.
    Games Reviews Previews Desktop Themes Downloads Paintball Forums Shareware Freeware and much more

    The best in Technology and Gaming News

    www.back2games.com

  6. #6
    Registered User
    Join Date
    Aug 2003
    Posts
    470
    nSize is the size of the array.
    Ok, you then want "nRightIndex = nSize - 1" instead of nRightIndex = nSize. You also must add code that correctly places the pivot.

  7. #7
    eat my shorts!
    Join Date
    Apr 2002
    Posts
    294
    added code::
    Code:
    		Swap ( panNumbers[nLeftIndex], panNumbers[0] );
    		if (panNumbers[nLeftIndex] < panNumbers[0])
    			return nLeftIndex;
    		else
    			return nLeftIndex-1;

    it works but with 1 mistake:
    ex:
    Code:
    Size of Array:12
    Range: 10
    
    Random Values:
    4 6 6 5 1 6 3 9 7 9 3 4
    Pivot: 4
    
    Left Side: 1 4 3 3 6
    MidPoint: 4
    Right Side: 5 9 7 9 6 6
    
    Final Array:
    1 4 3 3 6 4 5 9 7 9 6 6
    if u see above in the final array it swaps 1 with 4 and displays 3 after 4
    Last edited by dayknight; 09-17-2004 at 08:30 AM.
    Games Reviews Previews Desktop Themes Downloads Paintball Forums Shareware Freeware and much more

    The best in Technology and Gaming News

    www.back2games.com

  8. #8
    Registered User
    Join Date
    Aug 2003
    Posts
    470
    Code:
    int Partition(int* panNumbers, int nSize)
    {
        int nPivot = panNumbers[0];
        int nLeftIndex = 0;
        int nRightIndex = nSize - 1;
    
        while (nLeftIndex < nRightIndex)
        {
            while (panNumbers[nLeftIndex] <= nPivot 
                         && nLeftIndex < nRightIndex)
                nLeftIndex++;
    
            while(panNumbers[nRightIndex] > nPivot
                         && nLeftIndex < nRightIndex)
                nRightIndex--;
    
            // Because  panNumbers[nLeftIndex] > nPivot 
            // and panNumbers[nRightIndex] <= nPivot,
            // we may safely swap
    
            swap(panNumbers[nLeftIndex], panNumbers[nRightIndex]);
        }
    
        if (nLeftIndex > 1)
            swap(panNumbers[0], panNumbers[nLeftIndex - 1]);
    
        return (nLeftIndex > 1)? nLeftIndex - 1 : 0;      
    }
    Does this work?

  9. #9
    eat my shorts!
    Join Date
    Apr 2002
    Posts
    294
    it is 99% there, there is still 1 minor problem:
    final array:
    1 4 3 3 4 6 5 9 7 9 6 6


    and also could u plz explain me the return?, like wat exactly it is doing
    Last edited by dayknight; 09-17-2004 at 11:32 AM.
    Games Reviews Previews Desktop Themes Downloads Paintball Forums Shareware Freeware and much more

    The best in Technology and Gaming News

    www.back2games.com

  10. #10
    Registered User
    Join Date
    Aug 2003
    Posts
    470
    dayknight, I think this is what the final array is supposed to look like after partioning. Partioning just means that everything left of the pivot, which is index 4, is less than the pivot and everything right of the pivot is greater than the pivot. It might be a good idea to try to prove the correctness of this partioning method to see if it's really correct, but I'm rather not up to the challenge.


    The return of the partioning method is an operator that evaluates differently based upon whether expression before the '?', the condition, is true. If the condition is true, then the operator evaluates to the expression inbetween the '?' and the ':'. If, however, the condition is false, the operator evaluates to the expression after the ':'.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. An interesting problem of qsort()
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 03-05-2008, 12:09 PM
  2. qsort() in Array of Pointer to String
    By vb.bajpai in forum C Programming
    Replies: 8
    Last Post: 06-16-2007, 04:18 PM
  3. trouble with qsort
    By qubit67 in forum C Programming
    Replies: 5
    Last Post: 04-29-2007, 10:23 PM
  4. Question About Using qsort
    By Zildjian in forum C Programming
    Replies: 3
    Last Post: 11-04-2003, 03:17 PM
  5. C++ link error with qsort
    By bvnorth in forum C++ Programming
    Replies: 7
    Last Post: 10-24-2003, 02:22 AM