54. Listen: Sortieren II

Unser Sortieralgorithmus war ziemlich langsam. Es geht auch viel schneller, etwa mit folgendem Code:

static Node **getNodeArr(List *l, int *arrLen)
{
  Node **nodeArr, **arrEnt;
  Node *cur=l->first;

  *arrLen = list_len(l);
  if (!(nodeArr =malloc((*arrLen+1)*sizeof(Node*)))) {
    return NULL;
  }
  for (arrEnt=nodeArr; cur; cur=cur->next) {
    *arrEnt++ = cur;
  }
  return nodeArr;
}

static int nodeCompare(const void *a, const void *b)
{
  Node *node1=*(Node**)a, *node2=*(Node**)b;

  return strcoll(node1->cont, node2->cont);
}

Zwei Hilfsfunktionen: nodeCompare vergleicht die Strings in zwei Node-Pointern, getNodeArr füllt ein Array mit allen Node-Pointern der Liste – dieses Array kann mit leistungsfähigen Sortieralgorithmen sortiert werden. Wir verwenden qsort, ein Quicksort aus der C-Standardbibliothek.

int list_quicksort(List *l)
{
  int arrLen, i;
  Node **nodeArr=getNodeArr(l, &arrLen);
  Node *cur;

  if (!nodeArr) {
    return -1;
  }
  qsort(nodeArr, arrLen, sizeof(Node*), node_compare);

  cur = l->first = nodeArr[0];
  for (i=1; i<arrLen; i++) {
    cur->next = nodeArr[i];
    cur = cur->next;
  }
  nodeArr[arrLen-1]->next = NULL;
  l->last = cur;
  free(nodeArr);
  return 0;
}

Die Funktion qsort wird aufgerufen mit

1. Einem Pointer auf die Daten, die sortiert werden sollen
2. Der Anzahl der Datensätze
3. Der Größe eines Datensatzes
4. Einem Pointer auf eine Vergleichsfunktion, die zwei Pointer auf die Datensätze nimmt.

Man sieht, dass diese Quicksort-Implementation so in etwa alles nach allen denkbaren Kriterien sortieren kann, was im Speicher hintereinander in gleich großen Blöcken steht. Diese Flexibilität macht den Aufruf etwas kompliziert, und in der Regel will man sie auch gar nicht ausnutzen. Größe Speicherblöcke umherschieben kostet Zeit, und so will man meist nur Pointer auf die Speicherblöcke sortieren.

Das passiert auch hier – wir sortieren die Pointer im nodeArr, das wir uns eigens für diesen Zweck besorgen. Aus diesem Array bauen wir danach die Liste neu auf. Da nun die Vergleichsfunktion Pointer auf die Datensätze bekommt und unsere Datensätze Pointer sind, bedeutet das, dass nodeCompare Pointer auf Pointer bekommt, obwohl im Prototyp void * angegeben ist. Wir reparieren das über einen Cast, und es ist empfehlenswert, bei eigenen Vergleichsfunktionen diesem Muster zu folgen.

Die Mühe hat sich gelohnt: Die Laufzeit des Programms auf der letzten Folie reduziert sich mit dieser Funktion von 4 auf 0.4 Sekunden. Die Laufzeit der reinen Sortierfunktion hat sich noch drastischer von 3.68 auf 0.04 Sekunden reduziert – eine Verbesserung um einen Faktor 100, die bei größeren Datensätzen auch noch deutlicher ausfallen würde.