====== qsort() ======

''qsort()'' ist in der ''[[c:lib:stdlib:start|stdlib]]'' definiert, die in C über ''stdlib.h'', bzw in C++ über ''cstdlib'' eingebunden wird.

===== Funktion =====

''qsort()'' sortiert ein Array mit dem [[algo:Quicksort]]-Algorithmus.

===== Signatur =====

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

**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 ====

<code cpp>
#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;
}</code>

**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 [[c:lib:string:strcmp()]] Werte zurückgeben sollte. Entsprechend schreiben wir unsere eigene Vergleichsfunktion:

<code cpp>#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;
}</code>

**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:

<code cpp>#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;
}</code>

**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 =====

[[c:lib:stdlib:]]: [[bsearch()]]