ordinare in c

[s_p_81]

esempio:
classifica

roma=18
milan=19
napoli=12
lazio=15
inter=16
juventus=17

come si potrebbe editare il codice ordinandoli dalla squadra ke ha + punti a quella ke ne ha di -!Xò si tenga conto ke usando la funzione seed ogni volta ke lancio il programma i punti delle squadra variano?

[internet]

Usa la funzione standard qsort

#include <stdlib.h>
void qsort(void *base, size_t nmemb, size_t size,
           int (*compare)(const void *, const void *));

esempio

/* qsort example */
#include <stdio.h>
#include <stdlib.h>

int values[] = { 40, 10, 100, 90, 20, 25 };

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int main ()
{
  int n;

  qsort (values, 6, sizeof(int), compare);
 
 for (n=0; n<6; n++)
    printf ("%d ",values[n]);

  return 0;
}

Si potrebbe anche utilizzare un algoritmo più veloce, con complessità lineare O(N) visto che il punteggio ha un limite superiore basso, ma tale algoritmo non è presente nella librearia standard del C.

[infinitejustice]

x valori di n cosi piccoli anche un algoritmo con complessità quadratica va bene... (selectionsort per capirci)

...cmq la lineare nel sorting la ottieni solo con alcuni algoritmi nel solo caso migliore (gia ordinato), mai nel peggiore (quindi semmai un algoritmo con complessità Omega(n))

[internet]

No, esistono algoritmi di ordinamento in tempo O(N) nel caso peggiore
che non si basano sul confronto delle chiavi.

Ne conosco almeno 3
Counting sort
Bucket sort
Radix sort

Se hai il libro "Algoritmi di Cormen, Leyserson, Rivest" li trovi nel capitolo 9 dedicato agli ordinamenti in tempo lineare.

Nel problema della classifica si potrebbe usare il counting sort visto il limite superiore del punteggio è comunque basso, ed è di facile implementazione.

Il presupposto fondamentale su cui si basa è che le chiavi da ordinare siano limitate superiormente da un certo K che conosci e K = O(N).
(in questo caso 102)

E' vero però che il numero di elementi da ordinare è basso quindi un algoritmo con complessità Omega(N*log(N)) potrebbe essere più veloce in questo caso.

Comunque è utile conoscerli.

il counting sort
http://www.cse.iitk.ac.in/users/dsrk...ort/count.html

una animazione sul funzionamento del counting sort
http://www.cse.iitk.ac.in/users/dsrk...ntingSort.html

una lezione presa dal libro di cui sopra
http://www.dsi.unifi.it/~costa/lucid.../lezione10.ppt

[infinitejustice]

Beh dai miei ricordi di algoritmi e struct di dati counting sort è cmq limitato (interi o dati che possono essere espressi in una forma intera) ed aveva una complessità cui andava aggiunto un valore costante (che per n piccolo diventa significativo)

Anche radix ha una complessità legata a costanti (moltiplicative di n)ed è limitato alla possibilità di poter dividere gli elementi in sottoproblemi divisibili per due

Il terzo nn lo conosco x nulla
Gli altri due sono ottimi ma per n grandi ed hanno cmq quelle limitazioni