smistamento array di struct in c

Question

ho una struttura:

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

un array

list* B;

e un file di questi in modo di leggere nei file con questo

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);
}

ed un metodo di confronto

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;  

}

Vorrei una sorta stabile con nlog (n) forse merge sort in ordine di prie basso al più alto

ho solo bisogno i 20 prezzi più bassi.

Come potrei implementare questo usando il mio confronta con metodo?

grazie

Answer 1

Alla fine ho fatto questo utilizzando un conteggio sorta ci sono voluti più di 100 righe di codice in c.

Poi ho fatto in una sola riga in uno script di shell

sorta -nk 2,2 -s Wodehouse.txt | sorta -rnk 3,3 -s | sorta -rnk 1,1 -s | testa -20

Answer 2

  

Vorrei una stalla sorta con nlog (n) forse merge sort in ordine di prie basso al più alto

     

ho solo bisogno i 20 prezzi più bassi.

Poi si può fare questo in O (n). È possibile trovare i primi 20 valori in O (n) quindi ordinare quelli O (1).

Vedi qui per lo STL C ++ versione della libreria

implementazione Annotated Python qui

Answer 3

qsort è tuo amico :). (Mentre non è nlog (N) nel peggiore dei casi, è difficile fare fare qualcosa di più veloce)

Answer 4

Dal momento che lei ha citato C e non C ++, direi si considera implementare la propria versione di qualcosa di simile a qsort () .

Guardate come è definito il comparatore per qsort. Si avrebbe bisogno di definire qualcosa di simile per te stesso? Per l'ordinamento attuale, si avrebbe bisogno di implementare la propria versione di StableSort () da zero.

Answer 5

La funzione che si desidera utilizzare è qsort . C è dotato di una sorta perfettamente accettabile che esattamente quello che ti sembra di necessità.

qsort sé non è una specie stabile (beh, possono essere per una data implementazione, ma lo standard non garantisce esso), ma può essere realizzato in uno utilizzando trucchi. Ho fatto prima con l'aggiunta di un puntatore agli elementi dell'array, che è inizialmente popolato con l'indirizzo dell'elemento stesso (o un valore intero aumento, come si legge il file sarà probabilmente fare qui).

Quindi è possibile utilizzare che come chiave minore, che assicura elementi con la stessa chiave principale sono tenute in ordine.

Se non vuole andare alla difficoltà di cambiare le strutture, Algorithmist è un buon posto per ottenere il codice da . Io stesso, tendono a preferire piccole modifiche per re-implementazioni.

Per effettivamente rendere più stabile, modificare la struttura di:

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

e modificare il codice di lettura file:

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

allora la vostra funzione di confronto diventa qualcosa di simile:

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 6

Non c'è bisogno di qsort tutto. Basta creare un vuoto B * array per i 20 record più bassi, copiare i primi <= 20 record in là e qsort loro, se ci sono più di 20 poi come eseguire iterazioni sugli elementi li confronta con il più alto nei primi 20: se più di continuare il resto confrontare prossimo ecc indietro alto al più basso poi passare gli altri puntatori a spazio fare per il vostro prossimo ingresso nel low-20. Si ha bisogno di un confronto deterministico - ascoltare paxdiablo su questo fronte:. Aggiungere un numero record di ingresso o qualcosa da record differenziare

Answer 7

E 'a lievi modifiche alla funzione comparizon per rendere libreria qsort stabile. Vedi link qui

Qualcosa di simile al di sotto dovrebbe fare il trucco (non testato, essere prudenti):

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;
}

Questo potrebbe funzionare se si può garantire A e B sono nello stesso spazio di indirizzamento (due puntatori nella stessa matrice) e che ogni confronto danno un maggior ordinamento complessivo della matrice, gli indirizzi di strutture inferiori tenderà a diventare ancora più lenta . Questo è vero per le specie di bolla o simili. Che sarebbe anche lavorare per un'implementazione banale di QucikSort (che qsort non lo è). Tuttavia, per altri algoritmi, o qualsiasi algoritmo utilizzando lo spazio indirizzo aggiuntivo per l'archiviazione temporanea (forse a scopo di ottimizzazione), questa proprietà non sarà vero.

Se quello che contiene sorta qualsiasi identificatore univoco disponibile articoli a confronto (nell'esempio corrente che è probabilmente vero per ID campo), un altro metodo per rendere la scuderia tipo sarebbe quello di confrontare questi elementi. Si potrebbe anche aggiungere una chiave così unico in un nuovo campo a tal fine, ma in quanto utilizza più memoria si dovrebbe prendere in considerazione la terza opzione descritta di seguito prima di farlo.

Il mio metodo preferito sarebbe ancora una terza, non direttamente sorta una matrice di strutture, ma sorta un array di puntatori a elementi della struttura reali. Questo ha diverse proprietà buoni. In primo luogo è possibile confrontare le matrici della struttura indicavano, in quanto non cambierà e si farà la stalla tipo.

La funzione di confronto diventerà qualcosa come:

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;
}

Altre proprietà buona è che si evita strutture muoversi, mentre l'ordinamento puntatori, solo bisogno in movimento, e che può essere risparmio di tempo. È inoltre possibile mantenere molti di questi array puntatore, e che permetterà diversi accessi ordinato di elementi di matrice, allo stesso tempo.

svantaggi sono che richiede una certa memoria e che l'accesso agli elementi è leggermente più lenta (un livello di riferimento indiretto più).