# Thread: How to write my own qsort routine

1. ## How to write my own qsort routine

Hi All,

This is my first post to this group so bear with me please.

I've got a homework assignment to write my own version of the ANSI C qsort function. My qsort should mimic the ANSI C version and have the same prototype and behavior as qsort.

The prototype is as follows in my header file:
Code:
```extern void qsort_of( void *objects, int num, int size,
int (*cmp)(const void *, const void *) );```
The four tasks the instructor lined up are as follows:
1. Convert swap() to swap objects of any data types (not understood)
2. Compare data with function referenced by function pointer (understood)
3. Convert int * to void * and char * + size (not understood)
4. Modify parameter lists.

The instructor has given us a sample to use for guidance. That is as follows:
Code:
```void qsort_of( int * array, int count )
{
if ( count > 1 )
{
/* partition divides array in to two buckets
* then call qsort_of to recursively sort each bucket */
int pivot = partition( array, count );
qsort_of( array, pivot );
qsort_of( &array[pivot+1], count - (pivot+1) );
}
}

static int partition( int * array, int count )
{
int pivot = 0;
int inx = 0;

/* arbitrarily choose middle object as pivot
* and move it to head of the array. */
swap( &array[0], &array[count/2] );

/* loop through the rest of the array
* looking for objects smaller then pivot
* object.   If found move object to
* pivot - really lastsmall position */

for ( inx = 1; inx < count; num_cycles++,inx++ )
{
if ( array[inx] < array[0] )
{
swap( &array[++pivot], &array[inx] );
}
}

/* move pivot to partition position */
swap( &array[0], &array[pivot] );
return pivot;
}
static void swap( int * lo_obj, int * hi_obj )
{
if ( lo_obj != hi_obj )
{
int tmp = *lo_obj;
*lo_obj = *hi_obj;
*hi_obj = tmp;
num_swaps++;
}
}```
(print_ints left out intentionally)

What I'm confused on is what he means by "convert int* to void* and char*". Where am I supposed to do this conversion, in my qsort_of() or in swap()?

I'm guessing right now that the conversion should be in swap() and that swap() will have a prototype looking something like this:
Code:
`static void swap( void * lo_obj, void * hi_obj, int size );`
But I'm still confused on the part where we're supposed to convert int ptrs to void ptrs and char ptrs plus size. How is that accomplished?

So if someone understands what is expected of me, I would appreciate an explanation.

Small snippets of code are appreciated, as I want to see what it should look like, but I want to also do this myself. Psuedo code is good too. I'm having a hard time coming up with the design for this.
P.S. Pointers for better posting are appreciated.

2. Welcome to CBoard. First post is okay, ho hum.

1. Use a void* to pass arguments, so you can pass any type.

Do you have a good understanding of void pointers in C? It appears that your prof wants you to write a generic quicksort qoutine...

3. > 1. Convert swap() to swap objects of any data types (not understood)
Use the size parameter in the modified function prototype

> if ( array[inx] < array[0] )
Would be
if ( cmp( &array[inx], &array[0]) < 0 )
That is, you use the compare function to determine if two elements would be swapped.

> What I'm confused on is what he means by "convert int* to void* and char*".
The new function takes void*, so that it can be called easily with any type of parameter
So begin with
char *array = objects;

The arithmetic from then on is pretty easy
The first object is at array
The second object is at array + size;
The third object is at array + size * 2
ie, where you previously had array[n], you now have array[n*size]

4. Thanks Salem, that makes sense. I think I can work with that for now.