bsearch, qsort selbst bauen

Um nicht mit den Namen der Standardfunktionen zu kollidieren, werden in der folgenden Musterlösung andere Funktionsnamen verwendet, nämlich msearch() und msort().

// Time-stamp: "(31.10.01 19:28) msearchmsort.cpp [Klaus Wachtler (aw38)]"
//
// Lösung der Beispielaufgabe "Neuprogrammieren von bsearch() und qsort()".
//
// Diese Version läuft nur unter dem gcc, weil zum Allokieren von
// Speicherplatz die Funktion alloca() verwendet wird. Dies ist kein
// ANSI-Standard!


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

// sucht in einem sortierten Feld (*base)[] nach einem
// Element, für das die Funktion (*compar)() Gleichheit mit dem
// Schlüssel (*key) verspricht, und liefert einen Zeiger auf
// das gefundene Element, oder NULL
// (entspricht dem Original-bsearch() nach ANSI-C)
void *msearch( const void *key,
               const void *base,
               size_t nmemb,
               size_t size,
               int (*compar)( const void *, const void * )
               )
{
  switch( nmemb )
    {
    case 0:
      return NULL;
      
    case 1:
      return ( (*compar)( base, key )==0 ? (void *)base : NULL );
      
    default :
      
      // Teilen, und suchen lassen:
      {
        size_t n1 = nmemb/2;
        const void  *p1 = (const char*)base+(n1*size);
        int    v1 = (*compar)( p1, key );
        if( v1==0 )
          {
            // Schlüssel genau getroffen
            return(void *) p1;
          }
        else if( v1<0 )
          {
            // base[n1] kleiner als Schlüssel;
            // also in der oberen Hälfte suchen.
            // base[n1] braucht schon nicht mehr betrachtet
            // zu werden.
            return msearch( key,
                            (const char*)p1+size,
                            nmemb - n1 - 1,
                            size,
                            compar
                            );
          }
        else
          {
            // base[n1] größer als Schlüssel;
            // also in der unteren Hälfte suchen.
            // base[n1] braucht schon nicht mehr betrachtet
            // zu werden.
            return msearch( key,
                            base,
                            n1,
                            size,
                            compar
                            );
          }
      }

    } // switch

} // msearch()



// Aus c't 3/92, S. 263ff. entnommen:
// {Bezugsdatenstruktur a : ARRAY [1 .. n] und temp}
// 
// PROCEDURE quicksort ( links, rechts : integer);
// VAR k, i, j : integer;
// BEGIN
//    IF rechts > links THEN BEGIN
//       i := links -1; j := rechts; k := a[rechts].key;
//       REPEAT
//          REPEAT i := i +1 UNTIL a[i].key > k;
//          REPEAT j := j -1 UNTIL a[j].key <= k;
//          IF i >= j THEN
//          BEGIN
//             temp := a[i]; a[i] := a[r]; a[r] := temp;
//          END
//          ELSE
//          BEGIN
//             temp := a[i]; a[i] := a[j]; a[j] := temp;
//          END;
//       UNTIL i >= j;
//    quicksort( links, i-1 );
//    quicksort( i+1, rechts);
//   END;
// END;


void msort( const void *base,
            size_t nmemb,
            size_t size,
            int (*compar)( const void *, const void * )
            )
{
  // VAR k, i, j : integer;
  int i, j;
  void *key_p = alloca( size );

  // IF rechts > links THEN BEGIN
  if( nmemb>1 )
    { // Feldlänge größer als 1
      
      // i := links -1; j := rechts; k := a[rechts].key;
      i = -1; j = nmemb - 1;
      memcpy( key_p, (char*)base + size*j, size );

      // REPEAT
      do
        {

          // REPEAT i := i +1 UNTIL a[i].key > k;
          while( compar( (char*)base + size*++i, key_p )>0 );

          // REPEAT j := j -1 UNTIL a[j].key <= k;
          while( compar( (char*)base + size*--j, key_p )<=0 );

          // IF i >= j THEN
          if( i>=j )
            {
              // temp := a[i]; a[i] := a[r]; a[r] := temp;
              // ?
              // 31.10.2001 Klaus Wachtler:
              // Was hier vertauscht werden soll, weiß ich nicht.
              // Die Variable r ist bisher nicht erwähnt; ich nehme
              // an, daß nichts vertauscht werden muß.
              // Mein Beispielfeld jedenfalls wird richtig
              // sortiert.
              // Was wirklich gemeint ist, muß ich noch klären.
            }
          // ELSE
          else
            {
              // temp := a[i]; a[i] := a[j]; a[j] := temp;
              void *temp_p = alloca( size );
              memcpy( temp_p, (char*)base + size*i, size );
              memcpy( (char*)base + size*i, (char*)base + size*j, size );
              memcpy( (char*)base + size*j, temp_p, size );
            }

        }
      while( i<j ); // UNTIL i >= j;

      // quicksort( links, i-1 );
      msort( base, i-1, size, compar );

      // quicksort( i+1, rechts);
      msort( (char*)base + size*(i+1), nmemb - i - 1, size, compar );

    } // Feldlänge größer als 1
  

} // msort( const void *base,...


typedef struct
{
  double d;
  char   s[100];
} s_t;


// vergleicht zwei Elemente vom Typ s_t (auf welche
// die beiden übergebenen Zeiger zeigen) anhand ihrer
// darin enthaltenen Gleitkommawerte d:
int vergl_f( const void *p1, const void *p2 )
{
  if( ((const s_t*)p1)->d > ((const s_t*)p2)->d )
    {
      return 1;
    }
  else if( ((const s_t*)p1)->d < ((const s_t*)p2)->d )
    {
      return -1;
    }
  else
    {
      return 0;
    }
}


// zu sortierendes Beispielfeld:
s_t f[] =
{
  { 3.141592654, "pi" },
  { 2.718281828, "e" },
  { 53.00000000, "w" },
  { 1.000000000, "eins" },
  { 2.000000000, "zwoo" },
  { 13.00000000, "drölf" },
};


// Anzahl der Feldelemente:
const int l = sizeof(f)/sizeof(f[0]);


// Testprogramm:
int main( int nargs, char **args )
{
  qsort( f,
         l,
         sizeof(f[0]),
         vergl_f
         );

  //for( int i=0; i<l; i++ )
  //  {
  //    printf( "f[%2d]=%g\n", i, f[i].d );
  //  }


  while( 1 )
    {
      double wert;
      printf( "Bitte einen Wert: " );
      if( scanf( "%lf", &wert )!=1 )
        {
          break;
        }

      s_t key = { wert, "" };
      s_t *p = (s_t *)msearch( &key,
                               f,
                               l,
                               sizeof(f[0]),
                               vergl_f
                               );
      
      if( p )
        {
          printf( "Gefunden: %f %s\n", p->d, p->s );
        }
      else
        {
          printf( "nichts gefunden!\n" );
        }

    }

  return 0;

} /* main( int nargs, char **args ) */