How to write my own qsort routine

This is a discussion on How to write my own qsort routine within the C Programming forums, part of the General Programming Boards category; Hi All, This is my first post to this group so bear with me please. I've got a homework assignment ...

  1. #1
    Registered User
    Join Date
    May 2006
    Posts
    2

    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.

  2. #2
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    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...
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,443
    > 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]
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  4. #4
    Registered User
    Join Date
    May 2006
    Posts
    2
    Thanks Salem, that makes sense. I think I can work with that for now.

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, 11:09 AM
  2. Replies: 5
    Last Post: 03-18-2006, 10:25 AM
  3. Reroute where programs write to
    By willc0de4food in forum C Programming
    Replies: 7
    Last Post: 09-21-2005, 04:48 PM
  4. C++ link error with qsort
    By bvnorth in forum C++ Programming
    Replies: 7
    Last Post: 10-24-2003, 02:22 AM
  5. Qsort
    By Tombear in forum C Programming
    Replies: 1
    Last Post: 10-28-2001, 08:06 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21