Thread: Sorting strings to speed up search?

You could consider using qsort to sort the array of pointers to strings, then using bsearch to search the array.

Use the same compare function for both calls. It's pretty efficient if you do more searching than sorting.

Both functions are in stdlib.h

An example using ints as the data type

Code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define A_SIZE  50

int compare ( const void *a, const void *b ) {
    const int *pa = a;
    const int *pb = b;
    if ( *pa < *pb ) return -1;
    if ( *pa > *pb ) return +1;
    return 0;
}
void print_arr ( int *arr ) {
    int i;
    for ( i = 0 ; i < A_SIZE ; i++ ) {
        printf( "%2d ", arr[i] );
        if ( (i+1) % 10 == 0 ) printf( "\n" );
    }
    printf( "\n" );
}

int main ( ) {
    int test[A_SIZE];
    int i;
    int key, *result;

    // get some test data
    srand( time(NULL) );
    for ( i = 0 ; i < A_SIZE ; i++ ) {
        test[i] = rand() % 100;
    }
    print_arr( test );

    // sort the array using some compare function
    qsort( test, A_SIZE, sizeof(test[0]), compare );
    print_arr( test );

    // search the array,
    //   using a key of the same type,
    //   and the same compare function
    key = rand() % 100;
    result = bsearch( &key, test, A_SIZE, sizeof(test[0]), compare );
    if ( result ) {
        printf( "Found %d\n", *result );
    } else {
        printf( "Not found %d\n", key );
    }
    return 0;
}

Hint: here's a compare function too:

Code:

int compare(const void *i, const void *j) 
  { 
     
    return( strcmp(*(char **)i, *(char **)j) ); 

  }

You could use STL vector or list for the container and then STL sort() and binary_search() - in algorithm header. If you need general searching and sorting algorithms you'll be hard pushed to beat these for speed (due to the inlining of the comparison function they'll be faster than qsort).

> But the problem is that those functions only work with fixed length arrays.
They also work with variable length arrays

If you replace
  int test[A_SIZE];
with
  int *test = malloc( sizeof(int) * A_SIZE );

Then you're on your way to creating a variable sized array.

Or do as zen says

> One other question, maybe a stupid one, but why use char ** instead of char * in the compare function (and also in the bsearch and qsort)? Can't you just pass a char * to it, that's also a pointer...
Because the compare function is passed pointers to two elements of the array being sorted/searched. Since the array already contains pointers (char*), you get a pointer to a pointer (char**) inside the compare function.