Advanced   Java   Services

bsearch und qsort

Mit der Funktion qsort stellt stdlib.c eine äußerst schnelle Sortierfunktion zur Verfügung, die beliebige Arrays sortieren kann. Ebenso ist bsearch aus stdlib.c eine sehr performante Suchfunktion die Arrays beliebigen Typs nach einem Element durchsuchen kann, vorausgesetzt das Array ist sortiert. Beiden Funktionen muß ein Funktionspointer auf eine Vergleichsfunktion übergeben werden.

Alsa erstes sortieren wir ein Array von 10 int-Zahlen. Wir besorgen Speicher mit malloc, der zufällige Werte enthält. Diese sortieren wir.

Hier als erstes die Vergleichsfunktion für die aufsteigende Sortierung.

int compareInt(const void * i1, const void * i2)
{
   return (*(int*) i1 - *(int*) i2);
}

Das Beispiel

void qsortDemo()
{
   puts("qsortdemo");

   #define MAX 10
   int* iArr = (int*)malloc(MAX*sizeof(int));
   if (iArr == NULL) return;
   printf("unsortiert: ");
   for (int i = 0; i < MAX; i++)
      printf("%d ", iArr[i]);

   printf("\n");
   printf("sortiert  : ");
   qsort(iArr, MAX, sizeof(int), compareInt);

   for (int i = 0; i < MAX; i++)
      printf("%d ", iArr[i]);

   printf("\n");

Eine mögliche Ausgabe

qsortdemo
unsortiert: 4083008 4063608 1835102823 1701603654 977485171 1869762652 1835102823 1197237613 1768254821 1835103086
sortiert  : 4063608 4083008 977485171 1197237613 1701603654 1768254821 1835102823 1835102823 1835103086 1869762652

Um bsearch anzuwenden müssen wird zuerst sortieren. Wir erzeugen mit dem Zufallsgenerato´r vierzig zweistellige Zahlen zwischen 10 und 99 und sortieren sie. Anschließend suchen wir die Zahl 42. Als Vergleichsfunktion nehmen wir die des vorigen Beispiels.

void bsearchDemo()
{
   puts("bsearchdemo");

   #define ARRSIZE 40
   int iArr[ARRSIZE];
   // Zufallsgenerator mit Hilfe des aktuellen Datums initialisieren
   srand (time(NULL));
   // Zufallszahlen generieren und ausgeben
   printf("unsortiert: ");
   for(int i = 0; i<ARRSIZE; i++)
   {
      iArr[i] = 10 + rand()%90;
      printf("%d ", iArr[i]);
   }
   printf("\n");

   // Sortieren und ausgeben
   printf("sortiert  : ");
   qsort(iArr, ARRSIZE, sizeof(int), compareInt);
   for(int i = 0; i<ARRSIZE; i++)
      printf("%d ", iArr[i]);
   printf("\n");

   // Suchen
   int toSearch = 42;
   int* found = bsearch(&toSearch, iArr, ARRSIZE, sizeof(int), compareInt);
   if(found)
   {
      printf("zahl %d gefunden\n", *found);
      int i = found - iArr;
      printf("index ist %d\n", i);
   }
   else
   {
      printf("zahl %d nicht gefunden", toSearch);
   }
}

Hier zwei Ausgaben

bsearchdemo
unsortiert: 79 50 23 47 48 84 21 68 64 44 25 92 19 97 12 44 69 43 24 70 45 37 35 75 28 37 11 52 76 53 43 87 53 56 28 24 71 44 96 33
sortiert  : 11 12 19 21 23 24 24 25 28 28 33 35 37 37 43 43 44 44 44 45 47 48 50 52 53 53 56 64 68 69 70 71 75 76 79 84 87 92 96 97
zahl 42 nicht gefunden

bsearchdemo
unsortiert: 10 98 31 79 24 91 62 15 82 38 36 60 74 36 72 75 46 39 62 59 86 31 29 97 59 99 96 19 97 67 81 91 16 38 59 92 20 63 42 62
sortiert  : 10 15 16 19 20 24 29 31 31 36 36 38 38 39 42 46 59 59 59 60 62 62 62 63 67 72 74 75 79 81 82 86 91 91 92 96 97 97 98 99
zahl 42 gefunden
index ist 14