5 Replies - 2494 Views - Last Post: 19 October 2011 - 03:00 AM Rate Topic: -----

#1 Ajgilzean  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 64
  • Joined: 27-July 10

Quicksort using void pointers

Posted 19 October 2011 - 01:01 AM

Hey all. I have a working Quicksort function below that takes a pointer to an array of type ItemType. This type is of course defined by the user. I know it seems like a lot of code to read, but I would really appreciate any help with assisting me in converting these functions to using void pointers.

void Quicksort( ItemType* base, size_t nelem, int (*fcmp)( const ItemType&, const ItemType& ) )
{
  if( nelem<=1 ) return;
  
  size_t pivot = Partition( base, nelem, fcmp );
  
  unsigned LHS = pivot;
  unsigned RHS = nelem - (LHS+1);
  
  if( LHS!=0 )
    Quicksort( base, LHS, fcmp );
  if( RHS!=0 )
    Quicksort( (base+pivot+1), RHS, fcmp );
}

// Partition has a pivot and a oe/other end. If one element is out of order
// then pivot and oe switch. This means pivot is on the right and oe is on the
// left. Starting off, pivot_on_left=true but every time it has to switch with oe
// pivot_on_left becomes false. After a swap, oe moves one element closer to pivot.
size_t Partition( ItemType* base, size_t nelem, int (*fcmp)( const ItemType&, const ItemType& ) )
{
  int pivot = 0;
  bool pivot_on_left=true;
  int oe = (int)(nelem-1);
  
  while( pivot!=oe )
  {
    // If (pivotleft and out of order) OR (if pivotright and ooo)
    if( (pivot_on_left && (fcmp(base[pivot], base[oe])>0)) || (!pivot_on_left && (fcmp(base[pivot], base[oe])<0)) )
    {
      //swap( *pivot, *oe );
      ItemType temp = base[pivot];
      base[pivot] = base[oe];
      base[oe] = temp;
      //swap( pivot, oe );
      int ptemp = pivot;
      pivot = oe;
      oe = ptemp;
      
      pivot_on_left = !pivot_on_left; 
    }
    
     // oe moves towards pivot
    if( pivot_on_left  ) oe--;
    if( !pivot_on_left ) oe++;
  }
}




Now in a separate project I am trying to generalize my Quicksort function with the use of void pointers. I have also defined a few other functions to help assist Quicksort with void pointers. They look as follows.

// Swaps two entire array elements using size w
// w will be passed in through main as sizeof(ItemType)
void swap( void* a, void* b, size_t w)
{
  char* ch1 = reinterpret_cast<char*>(a);
  char* ch2 = reinterpret_cast<char*>(B)/>;
  
  for(unsigned i=0; i<w; i++)
  {
    char temp = ch1[i];
    ch1[i]=ch2[i];
    ch2[i]=temp;    
  }
}

// Assists in moving oe one unit closer to pivot. If the bool
// is true, then pivot is on left and oe moves left towards pivot.
// The opposite for pivot on right.
void move( void*& a, size_t w, bool b )
{
  reinterpret_cast<char*&>(a) += (B)/>? w:-w;
}





Now my real problem is coming back to the Quicksort and Partition function for void pointers, I can't seem to figure out how to apply my swap() and move() functions. This is the code I have for Quicksort() which takes a void pointer. It seems clear to me I am doing something wrong because I really don't understand what I'm trying to do at this point. Thanks again if you read all the way through!

void Quicksort( void* base, size_t nelem, size_t width, int (*fcmp)( const void*, const void* ) )
{
  if( nelem<=1 ) return;
  
  size_t pivot = Partition( base, nelem, width, fcmp );
  
  unsigned LHS = pivot;
  unsigned RHS = nelem - (LHS+1);
  
  if( LHS!=0 )
    Quicksort(base, LHS, width, fcmp );
  if( RHS!=0 )
    Quicksort( ((char*)base+pivot+1), RHS, width, fcmp );
}



Is This A Good Question/Topic? 0
  • +

Replies To: Quicksort using void pointers

#2 Salem_c  Icon User is offline

  • void main'ers are DOOMED
  • member icon

Reputation: 1635
  • View blog
  • Posts: 3,111
  • Joined: 30-May 10

Re: Quicksort using void pointers

Posted 19 October 2011 - 01:35 AM

> 13 Quicksort( ((char*)base+pivot+1), RHS, width, fcmp );
When you do address arithmetic on a pointer type, the compiler automatically scales things by the size of whatever the pointer points to.
int array[10];
int *p = a;
p = p + 1;
// p now points to array[1]


This is regardless of whether the compiler has 2, 4 or 8 byte integers, it works the same on all machines.


But when you're doing your own address arithmetic with void*, you also need to know how big the real type is (that's the additional width you're passing around.

So it's something like
Quicksort( ((char*)base+((pivot+1)*width), RHS, width, fcmp );
Was This Post Helpful? 0
  • +
  • -

#3 Ajgilzean  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 64
  • Joined: 27-July 10

Re: Quicksort using void pointers

Posted 19 October 2011 - 01:47 AM

View PostSalem_c, on 19 October 2011 - 01:35 AM, said:

But when you're doing your own address arithmetic with void*, you also need to know how big the real type is (that's the additional width you're passing around.

So it's something like
Quicksort( ((char*)base+((pivot+1)*width), RHS, width, fcmp );

That makes perfect sense! It needs to be multiplied by width because that will tell me the correct scaling.

Now for Partition(), thinking along the same terms, this means I should multiply by width when necessary? This is a rough attempt of what I am coming up with. Swap and move both take care of the scaling for me, so pivot and oe can remain integers correct?
size_t Partition( void* base, size_t nelem, size_t width, int (*fcmp)( const void*, const void* ) )
{
  int pivot = 0;
  bool pivot_on_left=true;
  int oe = (int)(nelem-1);
  
  while( pivot!=oe )
  {
    // If (pivotleft and ooo) OR (if pivotright and ooo)
    if( (pivot_on_left && (fcmp( (char*)(base+(pivot*width) ), (char*)(base+(oe*width)>0)))  // still getting an error here
                          || 
      (!pivot_on_left && (fcmp(base[pivot], base[oe])<0)) ) // will fix this, but will be similar to above
    {
      //swap( *pivot, *oe );
      swap(base+pivot, base+oe, width);
      //swap( pivot, oe );
      int ptemp = pivot;
      pivot = oe;
      oe = ptemp;
      
      pivot_on_left = !pivot_on_left; 
    }
    
     // oe moves towards pivot
     move(oe,width,pivot_on_left);
  }
}


This post has been edited by Ajgilzean: 19 October 2011 - 01:53 AM

Was This Post Helpful? 0
  • +
  • -

#4 Ajgilzean  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 64
  • Joined: 27-July 10

Re: Quicksort using void pointers

Posted 19 October 2011 - 02:16 AM

I am down to what I think is my last problem. This line is giving me an error which makes sense. What I am trying to do is to get oe to move closer to pivot. But the problem is that oe is an integer, it's not even a pointer.
move(base+oe, width, pivot_on_left);


Should I just scrap move() and try a different way to increment or decrement oe? My instructor provided this move() function so I thought it may have been useful.

This post has been edited by Ajgilzean: 19 October 2011 - 02:30 AM

Was This Post Helpful? 0
  • +
  • -

#5 Salem_c  Icon User is offline

  • void main'ers are DOOMED
  • member icon

Reputation: 1635
  • View blog
  • Posts: 3,111
  • Joined: 30-May 10

Re: Quicksort using void pointers

Posted 19 October 2011 - 02:51 AM

It's the same idea - you have a pointer + offset (or array[index])
All need to be converted in the manner described.
Was This Post Helpful? 0
  • +
  • -

#6 Ajgilzean  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 64
  • Joined: 27-July 10

Re: Quicksort using void pointers

Posted 19 October 2011 - 03:00 AM

I have a successful program! Timing it is nearly 2.5x slower than qsort() but that will do just fine. Thanks for the help. :bigsmile:
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1