./Source/util.c

Utilities/RB_QuickSort [ Functions ]

FUNCTION

Sort an array of pointers according to the lexical order of the elements the pointers point to. This is based on the quicksort routine in "The C programming language" by B Kerninghan en D Ritchie.

INPUTS

array -- the array of pointers.
left -- the most left element in the array.
right -- the most right element in the array.
f -- pointer to a function that can compare the objects two elements of the array point to.

RESULT

array -- A sorted array of pointers.

EXAMPLE

The following is an example program that shows the use

    #define TEST_SIZE 10

    char* test[ TEST_SIZE ] = { "ape", "zebra",
       "duck", "goofbal", "dodo", "rabit",
       "crow", "cow", "pig", "goat" };

    int string_compare( void* p1, void* p2 )
    {
       char *cp1 = p1;
       char *cp2 = p2;
       return strcmp( cp1, cp2 );
    }

    RB_QuickSort( test, 0, TEST_SIZE - 1, string_compare );

SOURCE

void RB_QuickSort(
    void **array,
    int left,
    int right,
    TCompare f )
{
    int                 i;
    int                 last;

    if ( left >= right )
    {
        return;
    }

    RB_Swap( array, left, ( left + right ) / 2 );
    last = left;
    for ( i = left + 1; i <= right; ++i )
    {
        if ( ( *f ) ( array[i], array[left] ) < 0 )
        {
            RB_Swap( array, ++last, i );
        }
    }
    RB_Swap( array, left, last );
    RB_QuickSort( array, left, last - 1, f );
    RB_QuickSort( array, last + 1, right, f );
}