Sortierfunktion in C

Verwenden Sie die C-Standardbibliotheksfunktion qsort, um ein Array zu sortieren. Übergeben Sie das Array, seine Elementanzahl, die Größe jedes Elements und eine Vergleichsfunktion, die die Reihenfolge festlegt.

Ein Integer-Array mit qsort sortieren

Die Vergleichsfunktion erhält Zeiger auf zwei Elemente vom Typ const void *. Wandeln Sie jeden Zeiger in einen Zeiger auf den Elementtyp um und vergleichen Sie anschließend die Werte. Sie muss einen Wert kleiner als null zurückgeben, wenn das erste Element in der Sortierreihenfolge vor dem zweiten steht, null, wenn die Elemente gleichwertig sind, oder einen Wert größer als null, wenn das erste Element danach steht. Vermeiden Sie die Rückgabe von left - right: Bei weit auseinanderliegenden int-Werten kann diese Subtraktion überlaufen und eine falsche Reihenfolge ergeben. Explizite Vergleiche umgehen dieses Problem.

Beim Aufruf ist das erste Argument das Array, das zweite seine Elementanzahl, das dritte die Größe eines Elements in Byte und das vierte die Vergleichsfunktion. sizeof values[0] bindet die Elementgröße an den Elementtyp des Arrays. qsort ordnet das übergebene Array direkt um. Wenn Sie es anschließend ausgeben, sehen Sie die sortierte Reihenfolge. Die Sortierung ist nicht stabil: Es ist nicht garantiert, dass gleichwertige Elemente ihre ursprüngliche relative Reihenfolge beibehalten.

Führen Sie dieses Beispiel aus:

Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.

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

static int compare_ints(const void *a, const void *b) {
  const int left = *(const int *)a;
  const int right = *(const int *)b;
  return (left > right) - (left < right);
}

int main(void) {
  int values[] = {53, 32, 12, 52, 87, 43, 93, 23};
  const size_t count = sizeof values / sizeof values[0];

  qsort(values, count, sizeof values[0], compare_ints);
  for (size_t i = 0; i < count; ++i) {
    printf("%s%d", i == 0 ? "" : " ", values[i]);
  }
  putchar('\n');
  return EXIT_SUCCESS;
}

Der Ausdruck (left > right) - (left < right) liefert eine der drei möglichen Ergebniskategorien für die Vergleichsfunktion, ohne mit den Eingabewerten zu rechnen. In diesem Beispiel bleiben das Array und seine Elementanzahl aufeinander abgestimmt. Wenn Sie das Array ändern, berechnen Sie die Anzahl anhand dieses Arrays, statt im Aufruf einen möglicherweise veralteten Zahlenwert stehen zu lassen.

Ein Zeichenketten-Array mit qsort sortieren

Ein Zeichenketten-Array ist häufig ein Array von Zeigern, zum Beispiel char *words[]. Jedes Element zeigt auf Zeichen; deshalb erhält die Vergleichsfunktion die Adresse dieses Zeigers. Sie muss den Zeiger auf das Arrayelement dereferenzieren, bevor sie die beiden Zeichenketten an strcmp übergibt. Da strcmp entsprechend der lexikografischen Reihenfolge bereits einen negativen Wert, null oder einen positiven Wert zurückgibt, kann das Ergebnis direkt als Rückgabewert der Vergleichsfunktion dienen.

Die Elementgröße ist hier sizeof words[0]. Sie entspricht der Größe eines char *, nicht der Länge des Textes. qsort verschiebt die Zeiger im Array; die Zeichen in den Zeichenkettenliteralen werden weder kopiert noch neu angeordnet. Die Reihenfolge richtet sich nach dem byteweisen Vergleich durch strcmp, der sich für eine gewöhnliche, nach Groß- und Kleinschreibung unterscheidende Sortierung eignet.

Führen Sie dieses Beispiel aus:

Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.

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

static int compare_strings(const void *a, const void *b) {
  char *const *left = (char *const *)a;
  char *const *right = (char *const *)b;
  return strcmp(*left, *right);
}

int main(void) {
  char *words[] = {"jello", "hello", "mello", "zello", "aello"};
  const size_t count = sizeof words / sizeof words[0];

  qsort(words, count, sizeof words[0], compare_strings);
  for (size_t i = 0; i < count; ++i) {
    printf("%s%s", i == 0 ? "" : " ", words[i]);
  }
  putchar('\n');
  return EXIT_SUCCESS;
}

Kommandozeilenargumente mit qsort sortieren

Mit derselben Vergleichsfunktion für Zeichenketten lassen sich die Argumente sortieren, die einem Programm übergeben werden. In main enthält argv[0] den Programmnamen; argv + 1 zeigt daher auf die erste vom Benutzer übergebene Zeichenkette. Auch der Programmname wird bei argc mitgezählt. Somit ist argc - 1 die Anzahl der vom Benutzer übergebenen Zeichenketten. Prüfen Sie die Anzahl vor dem Sortieren, damit das Beispiel mindestens zwei Werte zum Ordnen hat. Bei der Übergabe dieses Bereichs an qsort ändert sich die Reihenfolge der Argumentzeiger in argv, nicht aber der Inhalt der Zeichenketten.

Dieses vollständige Programm gibt einen Verwendungshinweis aus und wird erfolgreich beendet, wenn weniger als zwei Zeichenketten übergeben wurden. Andernfalls gibt es die übergebenen Zeichenketten in sortierter Reihenfolge aus. Kompilieren Sie es als C-Programm und übergeben Sie die zu sortierenden Wörter als Kommandozeilenargumente.

Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.

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

static int compare_strings(const void *a, const void *b) {
  char *const *left = (char *const *)a;
  char *const *right = (char *const *)b;
  return strcmp(*left, *right);
}

int main(int argc, char *argv[]) {
  if (argc < 3) {
    puts("Usage: program string_1 string_2 [string ...]");
    return EXIT_SUCCESS;
  }

  char **strings = argv + 1;
  const size_t count = (size_t)(argc - 1);
  qsort(strings, count, sizeof strings[0], compare_strings);

  for (size_t i = 0; i < count; ++i) {
    printf("%s%s", i == 0 ? "" : " ", strings[i]);
  }
  putchar('\n');
  return EXIT_SUCCESS;
}