Gibt es eine gute Bibliothek für eine große Palette von Zahlen in C Sortierung?

Question

Wenn ich eine große Reihe von ganzen Zahlen oder Schwimmer haben, was ist ein guter Algorithmus / Implementierung für die Sortierung (in C)?

Es ist ein bisschen spät im Spiel für eine bearbeiten ... aber ich bin auf der Suche für die Richtigkeit und Geschwindigkeit .

Answer 1

Für Arrays von Zahlen sortieren, einen Radixsort Algorithmus betrachten. Wenn sie richtig entwickelt, sollte diese Art eine bessere Leistung als GLIBC qsort bieten ().

Die usort Bibliothek enthält typspezifische Implementierungen für alle wichtigen C numerischen Typen.

http://bitbucket.org/ais/usort/wiki/Home

Der Geschwindigkeitsvorteil von Radixsort über GLIBC qsort ist etwa 2,5-fach für doppelte Genauigkeit Punktzahl bei N floating = 1000000 auf meinem 64-Bit-Intel-Laptop. Jedoch, wie N den Vorteil, sollte noch größer wächst seit Radixsort ein linearer Algorithmus erfordert konstante Anzahl von Durchgängen durch die Daten vorhanden ist.

Bei sehr kleinen N, entsendet den gleichen Code zu einem Introsort oder Insertionsort.

Answer 2

qsort () aus der Standardbibliothek ist eine gute UNO.

Die Vergleichsfunktionen wäre trivial für diese Fälle:

int cmp_int(const void *a, const void *b)
{
    const int *ia = a;
    const int *ib = b;

    if (*ia < *ib)
        return -1;

    if (*ia > *ib)
        return 1;

    return 0;
}

int cmp_float(const void *a, const void *b)
{
    const float *fa = a;
    const float *fb = b;

    if (*fa < *fb)
        return -1;

    if (*fa > *fb)
        return 1;

    return 0;
}

(EDIT:. Die Version davon basiert auf Subtrahieren b von einem auf unterzeichnet Überlaufverhalten beruht, so ist es keine gute Idee)

Answer 3

Es ist nie eine schlechte Idee zu benutzen qsort ... wenn Sie etwas über die Zahlen kennen.

Sie haben mit Radixsort markiert. Wie viel Speicher sind Sie bereit zu investieren? Sind die Zahlen in einem bestimmten Bereich? Haben sie Eigenschaften, die Radix Sortier- machbar?

macht

Wenn Sie nicht viel Speicher verwenden möchten, qsort ist eine gute Option.

Answer 4

eine riesige Menge an RAM Da wir heutzutage immer, die folgenden Satz Art möglich: für jede Zahl das Bit in einem großen RAM-Bit-Array markieren Sie haben, sie dann durch Abtasten der RAM abgelesen zurück. Viele Hardware-spezifische Optimierungen können für die Markierung und Scan Phasen angewendet werden.