Sorting in C: swapping pointers leads to unexpected results

Question

At the start of the programm, I allocate memory for an array of char-pointers:

char **buffer = calloc( 20, sizeof(char *) );

Then the user can input up to 20 words:

buffer[i] = calloc( 40, sizeof(char) );
fgets( buffer[i], 40, stdin )`

Afterwards I want to sort this array. It works as expected if I use my swap function as follows:

void swap(char *args1, char *args2) {
    char tmp[40];
    strcpy( tmp, args1 );
    strcpy( args1, args2 );
    strcpy( args2, tmp );
}

void sort( char **args, int count ) {
    ...
    swap( args[i], args[j] );
    ...
}

After thinking through this, I noticed that this was a waste of CPU since all I had to do was actually redirecting the pointers to the corresponding strings. So I rewrote my swap function:

void swap(char **args1, char **args2) {
    char *tmp = *args1;
    *args1 = *args2;
    *args2 = tmp;
}

void sort( char **args, int count ) {
    ...
    swap( &args[i], &args[j] );
    ...
}

However, this will not work at all, the results are extremely unexpected, I cannot figure out why (I tried several printf calls and whatnot)... My understanding was that the pointers are just redirected and thus swapped, let's say the memory looks like this:

(begin of char**):
100: *160
108: *200
116: *240
124: *280
...
(begin of char*):
160: Hello!\0
200: World!\0
...

My idea was to alter the pointers instead of the arrays for minimum CPU effort (Here: swap pointer in 100 with pointer in 108):

(begin of char**):
100: *200
108: *160
116: *240
124: *280
...
(begin of char*):
160: Hello!\0
200: World!\0
...

I tried to explain this as thorough as I could and I'm sorry if it's too much explanation. I would be most glad if someone could give me insight into this and help!

The full code (with the working strcpy) can be found here: http://pastie.org/5361481

Answer 1

Your sort function should end up looking like this:

void sort(char ** args, const int start, const int end) {
        char **pivot = &args[end];
        int i = start-1, j = start;
        while( j < end ) {
                int cmp = strcmp( *pivot, args[j] );
                if( cmp > 0 )
                        swap( &args[++i], &args[j] );
                j++;
        }
        swap( &args[++i], pivot );
        if( start + 1 < i )
                sort( args, start, i - 1 );
        if( end - 1 > i )
                sort( args, i + 1, end );
}

I suspect that you didn't make the pivot be a char**, but left it as a char*. If you do that, then whenever you do the swap, you aren't actually swapping two elements in your array, but rather swapping one element of the array with a local variable. The pivot variable ends up pointing to a different string instead of the last array member pointing to a different string.