Sortierung Array von Strukturen in c

Question

Ich habe eine Struktur:

typedef struct book{ 
    double rating; 
    double price; 
    double relevance; 
    int ID; 
}B; 

ein Array

list* B; 

und eine Datei von diesen lesen so in den Dateien mit diesem

int read_file(char* infile, int N) 
{ 
    int c; 
    if((fp=fopen(infile, "rb"))) 
    { 
     fscanf(fp, "%*s\t%*s\t%*s\t%*s\n"); 
     c=0; 
     while((!feof(fp))&&(c<N)) 
    { 
     fscanf(fp, "%lf\t%lf\t%lf\t%d\n", &list[c].rating, &list[c].price, &list[c].relevance, &list[c].ID); 
     c++; 
    } 

fclose(fp);  
    } 
    else 
    { 
     fprintf(stderr,"%s did not open. Exiting.\n",infile); 
     exit(-1); 
    } 
    return(c); 
} 

und eine Vergleichsmethode

int comp_on_price(const void *a, const void *b) 
{ 

    if ((*(B *)a).price < (*(B *)b).price) 
    return 1; 
    else if ((*(B *)a).price > (*(B *)b).price) 
    return -1; 
    else 
    return 0; 

} 

Ich möchte eine stabile Art mit nlog (n) Zeit vielleicht Art in der Reihenfolge der niedrigsten prie

i brauchen nur die 20 besten Preis zu höchsten fusionieren.

Wie würde ich dies mit meiner Vergleichsmethode implementieren?

dank

Answer 1

Ich habe schließlich dies mit einer Zählung Sortierung dauerte es über 100 Zeilen Code in c.

ich habe es dann in einer Zeile in einem Shell-Skript

sortieren -NK 2,2 -s Wodehouse.txt | sortieren -rnk 3,3 -s | sort -rnk 1,1 -s | head -20

Answer 2

qsort ist dein Freund :). (während es im schlimmsten Fall nicht Nlog (N) ist, ist es schwierig, etwas schneller zu machen)

Answer 3

Die Funktion, die Sie verwenden möchten, ist qsort. C kommt mit einer vollkommen akzeptablen Sortierung, die genau was Sie scheinen, braucht.

qsort selbst ist keine stabile Art (na ja, es für eine gegebene Implementierung sein kann, aber der Standard es ist keine Garantie), aber es kann mit einigen Tricks eines gemacht werden. Ich habe das schon gemacht, indem ich einen Zeiger auf die Array-Elemente hinzugefügt habe, der anfänglich mit der Adresse des Elements selbst gefüllt wurde (oder ein zunehmender ganzzahliger Wert beim Lesen der Datei wird wahrscheinlich hier geschehen).

Dann können Sie das als Moll-Schlüssel verwenden, der sicherstellt, dass Elemente mit demselben Dur-Schlüssel in der richtigen Reihenfolge bleiben.

Wenn Sie nicht wollen, um die Mühe der Änderung der Strukturen zu gehen, ist Algorithmist ein guter Ort, um get code aus. Ich selbst bevorzuge kleinere Änderungen an Re-Implementierungen.

Um tatsächlich stabil zu machen, Ihre Struktur ändern:

typedef struct book { 
    double rating; 
    double price; 
    double relevance; 
    int ID; 
    int seq;         // Added to store sequence number. 
} B; 

und ändern Sie Ihre Datei Lesen Code:

fscanf(fp, "%lf\t%lf\t%lf\t%d\n", ... 
list[c].seq = c;       // Yes, just add this line. 
c++; 

dann Vergleichsfunktion wird so etwas wie:

int comp_on_price(const void *a, const void *b) { 
    B *aa = (B*)a; 
    B *bb = (B*)b; 

    if (aa->price < bb->price) 
     return 1; 
    if (aa->price > bb->price) 
     return -1; 
    return (aa->seq < bb->seq) ? 1 : -1; // Cannot compare equal. 
} 

Answer 4

Da Sie C und nicht C++ erwähnt haben, würde ich sagen, dass Sie überlegen, Ihre eigene Version von etwas Ähnliches wie qsort().

Schauen Sie sich an, wie der Komparator für qsort definiert ist. Sie müssten etwas ähnliches für sich definieren? Für die eigentliche Sortierung müssten Sie Ihre eigene Version von StableSort() von Grund auf neu implementieren.

Answer 5

Ich möchte eine stabile Art mit nlog (n) Zeit vielleicht Art verschmelzen in der Reihenfolge der niedrigsten prie höchsten

ich brauche nur die 20 günstigsten Preisen anzubieten.

Dann können Sie dies in O (n) Zeit tun. Sie können die ersten 20 Werte in O (N) Zeit finden und dann diese O (1) sortieren.

See here for the STL C++ library version

Annotated Python implementation here

Answer 6

Es ist nur eine leichte Änderungen an Ihrer comparizon Funktionsbibliothek qsort stabil zu machen. Siehe Link here

So etwas wie unten tun sollte den Trick (ungetestet, seien Sie vorsichtig):

int comp_on_price(const void *a, const void *b) 
{ 
    if ((*(B *)a).price < (*(B *)b).price) 
     return 1; 
    else if ((*(B *)a).price > (*(B *)b).price) 
     return -1; 
    else 
     // if zero order by addresses 
     return a-b; 
} 

Dies würde funktionieren, wenn Sie a und b in demselben Adressraum garantieren kann (zwei Zeiger im selben Array) und dass jeder Vergleich eine größere Gesamtordnung des Arrays ergibt, werden Adressen niedrigerer Strukturen dazu neigen, noch langsamer zu werden. Dies gilt für Blasensorten oder ähnliches. Das würde auch für eine triviale Implementierung von QucikSort funktionieren (was qsort nicht ist). Für andere Algorithmen oder jeden Algorithmus, der zusätzlichen Adressraum für temporäre Speicherung verwendet (möglicherweise für Optimierungszwecke), ist diese Eigenschaft nicht wahr.

Wenn das, was Sie sortieren, einen eindeutigen Bezeichner in verglichenen Elementen enthält (im aktuellen Beispiel wahrscheinlich für Feld-ID), wäre eine andere Methode, die Sortierung stabil zu machen, der Vergleich dieser Elemente. Sie könnten zu diesem Zweck auch einen solchen eindeutigen Schlüssel in einem neuen Feld hinzufügen, aber da er mehr Speicher verwendet, sollten Sie die dritte Option, die weiter unten beschrieben wird, beachten.

Meine bevorzugte Methode wäre immer noch eine dritte, sortiere nicht direkt ein Array von Strukturen, sondern sortiere ein Array von Zeigern auf tatsächliche Strukturelemente. Dies hat mehrere gute Eigenschaften. Zuerst können Sie Arrays der Struktur, auf die gezeigt wird, vergleichen, da sie sich nicht ändert und die Sortierung stabil macht.

Die Vergleichsfunktion wird sich so etwas wie:

int comp_on_price(const void *a, const void *b) 
{ 
    if ((*(B **)a)->price < (*(B **)b)->price) 
     return 1; 
    else if ((*(B **)a)->price > (*(B **)b)->price) 
     return -1; 
    else 
     // if zero, order by addresses 
     return *(B **)a-*(B **)b; 
} 

Andere gute Eigenschaften ist, dass es um Strukturen vermeiden bewegen, während das Sortieren, es müssen nur bewegende Zeiger, und das kann das spart Zeit sein. Sie können auch mehrere solcher Zeigerarrays behalten, die mehrere geordnete Zugriffe auf Array-Elemente gleichzeitig ermöglichen.

Nachteile sind, dass es etwas Speicher benötigt und dass der Zugriff auf Elemente etwas langsamer ist (eine Ebene der Indirektion mehr).

Answer 7

Sie müssen nicht alles abfragen. Erstellen Sie einfach ein leeres B * -Array für die 20 niedrigsten Datensätze, kopieren Sie die ersten < = 20 Datensätze dort und qsort sie, wenn es mehr als 20 dann beim Iterieren über Ihre Elemente mit dem höchsten in den ersten 20 vergleichen: if Dann fahre fort, vergleiche mit dem nächsthöheren usw. Zurück zum Niedrigsten und verschiebe dann die anderen Zeiger, um Platz für deinen nächsten Eintrag im Low-20 zu schaffen. Sie brauchen einen deterministischen Vergleich - hören Sie Paxdiablo an dieser Front: Fügen Sie eine Eingangsdatensatznummer oder etwas hinzu, um Datensätze zu unterscheiden.