qsort()

qsort() ist in der stdlib definiert, die in C über stdlib.h, bzw in C++ über cstdlib eingebunden wird.

Funktion

qsort() sortiert ein Array mit dem Quicksort-Algorithmus.

Signatur

#include <stdlib.h>
void qsort( void * array, size_t elementCount, size_t size, int (*compare)(const void *, const void *) );

array: Zeiger auf das erste Element des zu sortierenden Arrays
elementCount: Anzahl der Elemente im Array
size: Größe eines einzelnen Elementes
compare: Vergleichsfunktion, um zwei Elemente miteinander zu vergleichen.

Return Value: -

Die Vergleichsfunktion gibt -1 zurück, wenn der linke Parameter vor dem rechten Parameter einsortiert werden soll, 0, falls der linke und rechte Parameter gleichwertig sind und 1, falls der rechte Parameter vor dem linken einsortiert werden soll.

Soll in umgekehrter Reihenfolge sortiert werden, muss man eine Funktion schreiben, die den Vergleich negiert (oder die Parameter vertauscht).

Fehlerquellen

-

Beispiele

Strings

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int compare( void const * lhs, void const * rhs )
{
  char * left  = *((char **) lhs);
  char * right = *((char **) rhs);
 
  return strcmp( left, right );
}
 
int main (void)
{
  char const * dayOfWeek[] = { "Montag"
                             , "Dienstag"
                             , "Mittwoch"
                             , "Donnerstag"
                             , "Freitag"
                             , "Samstag"
                             , "Sonntag" };
  int i = 0;
 
  printf( "Originalreihenfolge:\n" );
  for( i = 0; i < 7; ++i )
    printf( "%d: %s\n", i, dayOfWeek[i] );
 
  qsort( dayOfWeek, 7, sizeof( char * ), compare );
 
  printf( "\nsortierte Reihenfolge:\n" );
  for( i = 0; i < 7; ++i )
    printf( "%d: %s\n", i, dayOfWeek[i] );
 
  return EXIT_SUCCESS;
}

Ausgabe

Originalreihenfolge:
0: Montag
1: Dienstag
2: Mittwoch
3: Donnerstag
4: Freitag
5: Samstag
6: Sonntag

sortierte Reihenfolge:
0: Dienstag
1: Donnerstag
2: Freitag
3: Mittwoch
4: Montag
5: Samstag
6: Sonntag

Buchstaben / Zahlen

Am Beispiel mit den Strings haben wir gesehen, dass die Vergleichsfunktion entsprechend strcmp() Werte zurückgeben sollte. Entsprechend schreiben wir unsere eigene Vergleichsfunktion:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int compare( void const * lhs, void const * rhs )
{
  char left  = *((char *) lhs);
  char right = *((char *) rhs);
 
  if( left < right ) return -1;
  if( left > right ) return  1;
 
  return 0;  /* left == right */
}
 
int main (void)
{
  char text[] = "proggen.org";
 
  printf( "Der originale Text: %s\n", text );
  qsort( text, strlen( text ), sizeof( char ), compare );
  printf( "Der sortierte Text: %s\n", text );
 
  return EXIT_SUCCESS;
}

Ausgabe

Der originale Text: proggen.org
Der sortierte Text: .egggnooprr

Strukturen

Auch ganze Strukturen lassen sich sortieren. Hier sortieren wir Personen zuerst nach dem Nachnamen, dann nach dem Vornamen. Finden sich Leute, die den gleichen Vor- und Nachnamen haben, so sortieren wir nach dem Alter:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
struct Person
{
  char * FirstName;
  char * FamilyName;
  int    Age;
};
 
int compare( void const * lhs, void const * rhs )
{
  struct Person * left  = ((struct Person *) lhs);
  struct Person * right = ((struct Person *) rhs);
 
  int result = strcmp( left->FamilyName, right->FamilyName );
  if( result )
    return result;
 
  result = strcmp( left->FirstName, right->FirstName );
  if( result )
    return result;
 
  if( left->Age < right->Age ) return -1;
  if( left->Age > right->Age ) return 1;
 
  return 0;
}
 
int main (void)
{
  struct Person figures[] = { { "Max", "Mustermann", 40 }
                            , { "Erika", "Mustermann", 38 }
                            , { "Erika", "Gabler", 38 }
                            , { "Erika", "Mustermann", 35 }
                            , NULL };
  int i = 0;
 
  printf( "Originalreihenfolge:\n" );
  for( i = 0; i < 4; ++i )
    printf( "%s, %s (%d)\n", figures[i].FamilyName, figures[i].FirstName, figures[i].Age );
 
  qsort( figures, 4, sizeof( struct Person ), compare );
 
  printf( "\nsortierte Reihenfolge:\n" );
  for( i = 0; i < 4; ++i )
    printf( "%s, %s (%d)\n", figures[i].FamilyName, figures[i].FirstName, figures[i].Age );
 
  return EXIT_SUCCESS;
}

Ausgabe:

Originalreihenfolge:
Mustermann, Max (40)
Mustermann, Erika (38)
Gabler, Erika (38)
Mustermann, Erika (35)

sortierte Reihenfolge:
Gabler, Erika (38)
Mustermann, Erika (35)
Mustermann, Erika (38)
Mustermann, Max (40)

siehe auch