# Quicksort using void pointers

Page 1 of 1

## 5 Replies - 6137 Views - Last Post: 19 October 2011 - 03:00 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=251938&amp;s=66c57c690882f3eeba3ac1cf09ffbcb8&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 Ajgilzean

Reputation: 1
• 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

• void main'ers are DOOMED

Reputation: 2131
• Posts: 4,196
• 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 );

### #3 Ajgilzean

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

## Re: Quicksort using void pointers

Posted 19 October 2011 - 01:47 AM

Salem_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

### #4 Ajgilzean

Reputation: 1
• 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

### #5 Salem_c

• void main'ers are DOOMED

Reputation: 2131
• Posts: 4,196
• 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.

### #6 Ajgilzean

Reputation: 1
• 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.

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }