Thread: 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.
If more info is needed, please let me know. Thanks.
P.S. Pointers for better posting are appreciated.

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