Newsgroup: it.comp.lang.c
Titolo: Ordinamento dei record di un file

Ciao a tutti e scusate per la mia domanda.
Come posso ordinare in visualizzazione un file; ovviamente i record del file
sono gestiti da una struttura che leggo attraverso la funzione
fread(p,sizeof(struct_libro), 1,fp). Volevo utilizzare la funzione di
libreria standard qsort(...) ma mi viene difficile. Qualcuno potrebbe
illuminarmi su ciň? Grazie a tutti.

 ha scritto nel messaggio
news:ac2k23$9op$1...@lacerta.tiscalinet.it...


 ha scritto nel messaggio
news:TAoF8.67895$zW3.1...@news1.tin.it...


algoritmi di ordinamento.
Ti faccio un analisi grezza dei costi prima:
Leggere tutti gli elementi e inserire (in testa o in coda, ma comunque
con un tempo costante) in una lista: O(N).
Ordinare una lista (con il qsort della stdlib magari): O(NlgN), anche
se il qsort ben implementato ha una costante inferiore a 1 (non
chiedevemi come si possa calcolare perche' non sono un teorico :P).
Leggere e inserire in una lista e inserire man mano in ordine: O(N^2)
Leggere e inserire in un albero binario di ricerca: da 0(N^2) se
l'albero era degenere (in pratica hai avuto sfiga a leggere, o era
gia' ordinato e ti e' uscita una lista) a O(N*lgN) se e' ben
bilanciato.
La soluzione piu' robusta e' quella mettere tutto in una lista e poi
ordinare con il qsort, ma solo se ti aspetti che il file possa essere
ordinato, se no usa un albero binario.
In C potresti usare il qsort su di una lista, o un albero o qualsiasi
cosa che non sia direttamente un array richiede un giochino un po'
sporco:
- usare un array di puntatori
- visitare la tua struttura e man mano memorizzare nell'array
- ordinare 
- ricrearti a posteriori la struttura (risistemare i link
fondamentalmente).
(RTF per maggiori informazioni)
E' complesso da fare, ma compensa perche' il qsort + l'overhead per
memorizzare il tutto nell'array e ricreare potrebbe essere ancora meno
costoso che non implementare un algoritmo di ordinamento proprio
(bisorrebbe fare dei test nella situazione specifica comunque).
-- 
Mox
"Trust the programmer."
"Don't prevent the programmer from doing what needs to be done."
"Keep the language small and simple."
"Provide only one way to do an operation."

- ricrearti a posteriori la struttura (risistemare i link fondamentalmente).
Ma tutto ciò non richiede un impiego troppo masiccio di memoria, 
specialmente per liste di una certa lunghezza? Se dovessi ordinare 
liste di una certa lunghezza quanto questo metodi sarebbe funzionale?
Non si potrebbe ordinare il tutto direttamente su file? E' vero, il
programma 
viene rallentato dall'accesso a disco, ma è anche vero che ciò sarebbe
fatibile impiegando poca memoria.
Io avevo pensato a qualcosa del genere:
	FILE *fp;
	struct campo campoa;
	struct campo campob;
	unsigned char pass, count;
	char flag;
	int n_campi;
	int compare(struct campo *, struct campo *);  //ritorna 0 se
già in ordine, 1 se invertiti
	fp=fopen("rubrica.dat", "rb+");
	if(fp==NULL)
		exit(0)
	else {
		for(pass=0; pass<(n_campi=number(fp))-1; pass++) {
			flag=0;
			rewind(fp);
			for(count=1; count<=n_campi-pass; count++)
			{
				fread(&campoa, sizeof(struct campo),
1, fp);
				fread(&campob, sizeof(struct campo),
1, fp);
				if(!compare(&campoa, &campob)) {
//ritorna 0 se già in ordine, 1 se invertiti
					flag=1;
					fseek(fp, -2*sizeof(struct
campo), SEEK_CUR);
					fwrite(&campob, sizeof(struct
campo), 1, fp);
					fwrite(&campoa, sizeof(struct
campo), 1, fp);
				}
				fseek(fp, -1*sizeof(struct campo),
SEEK_CUR);
			}
			if(!flag)
				break;
		}
		printf("Ordinamento terminato\n");
		fclose(fp);
	}
Applicando il bubble sort agli elementi del file ci sarebbero, è vero,
n!/2 (qualcuno mi 
corrgga se sbaglio) passaggi in media, ma d'altro canto, come si vede,
non richiedo
un grande impiego di memoria. Certo, bisogna tener sempre nel dovuto
conto le diverse
esigenze. E cmque probabilemnte si potrebbe usare qualche algoritmo
più efficiente del bubble sort(credo)!

piů efficiente del bubble sort(credo)!
A parte che esistono ordinamenti in tempo O(NlgN) e se hai un caso
particolare sottomano anche O(N), ma tu non hai considerato una cosa:
accedere al disco per leggere un file ha un costo altissimo, tra
scritture e letture.
Certo, il sistema di bufferizzazione interno del sistema potrebbe
evitare di farti leggere e scrivere direttamente su file se questo
viene contenuto interamente in memoria e la scrittura vera sara' solo
con il sync finale... ma potenzialmente e' un idea molto goffa (inteso
come prestazioni che rischiano di degenerare rapidamente).
Anche nei casi in cui si ordinano file che non possono essere
contenuti interamente in memoria si cerca comunque di sfruttare al
massimo la memoria disponibile e di effettuare tutte le operazioni li.
