Programma per ordinare alfabeticamente

[aguex]

Potreste spiegarmi come si fa un programma in c++ che ordini parole date dall'utente o su un file alfabeticamente? Non mi vuol proprio venire in mente...

[Insaponata]

prova ad associare ad ogni lettera dell'alfabeto un numero, ad ex: a=0, b=1, c=2, ecc...
in C lo puoi fare automaticamente: se fai
printf("%d", 'a');
ti stampa un numero corrispondente al codice ASCII della lettera 'a'. In C++ penso che sia lo stesso, ma non so: prova!

[lord mark 87]

ci sono molti algoritmi di ordinamento

purtroppo non posso aiutarti con un frammento di codice perchè non so usare c++, però ti posso consigliare di usare l'algoritmo di ordinamento del quicksort (magari dopo posto qualcosa, l'idea risolutiva...)

[Insaponata]

io ragionavo in C, e speravo di essere d'aiuto... cmq se ci sono le fun già fatte... meglio!

[aguex]

Grazie!

[aguex]

Però io volevo capire come fare, non che funzioni usare Vorrei capire come hanno fatto a programmare quelle funzioni. Elementer, in quel file nn viene spiegato come ordinare delle stringhe....

[Insaponata]

:-p

[aguex]

Il tuo metodo insaponata nn è valido, ci avevo già pensato, sarebbe troppo lungo. E poi le parole che iniziano con la stessa lettera....

[aguex]

Il quel file viene spiegato con quale funzione puoi fare il confronto lessicografico... se una stringa S1 è più grande di S2 vuol dire che S1 va prima di S2, se poi intendi dato un insieme di 100000 di stringhe come ordinarle.... puoi usare anche quelle funzioni, ma in mezzo agli algoritmi però...

ciao

Ahhh, non avevo capito, grazie

[janky]

 #include <iostream.h>
#include <string.h>
#include <stdio.h>

char stringa[20][80];
int n=3;
void ordina(int i);

void main()
{
	
	do
	{
		cout<<"\n\tQuante stringhe vuoi inserire? (max 20): ";
		cin>>n;
	}while(n<0||n>20);
	
	for(int i=0;i<n;i++)
	{	
		cout<<"\n\tinserisci la stringa: ";
		gets(stringa[i]);
	}

	ordina(n);

	for(i=0;i<n;i++)
	{
		cout<<"\n"<<stringa[i];
	}

}

void ordina(int i)
{

	if(i>0)
	{
	int j,a;
	char b[80];
	for(j=0;j<n-1;j++)
	{		
		for(a=0;a<80;)
		{
			if(stringa[j][a]<stringa[j+1][a])			//se la prima stringa è già minore della seconda esci
			{
				break;
			}
			if(stringa[j][a]==stringa[j+1][a])			//se il primo carattere è uguale aumenta il secondo indice per 
			{							//vedere se il secondo è minore o maggiore
				a++;
			}
			if(stringa[j][a]>stringa[j+1][a])			//se la prima è maggiore della seconda... 
			{
				strcpy(b,stringa[j]);				//...scambia i due array mediante una variabile di appoggio
				strcpy(stringa[j],stringa[j+1]);
				strcpy(stringa[j+1],b);
				break;
			}
		}
	}
	ordina(i-1);							//ricorsione della funzione
	}	
}

tò, scritto in 5 minuti, dovrebbe andare, non l'ho provato

[Insaponata]

in C vale la relazione
'a' < 'b';
quindi è su questo che ci si basa...

penso che Janky sia il più vicino alla soluzione!

[MiStO]

l'idea di janky(bubble sort) è buona per piccole quantità di dati da ordinare,ma al crescere dei dati in input il tempo di esecuzione aumenta in modo esponenziale(2 cicli for ti portano tempi intorno a n^n=n^2)...quindi se devi lavorare su,diciamo,max un centianio di stringhe medio corte ok,sennò ti conviene guardarti qualche altro ordinamento(quick sort o heap sort:un po' +complessi da implementare ma sicuramente migliori in termini di complessità computazionale)

[janky]

l'idea di janky(bubble sort) è buona per piccole quantità di dati da ordinare,ma al crescere dei dati in input il tempo di esecuzione aumenta in modo esponenziale(2 cicli for ti portano tempi intorno a n^n=n^2)...quindi se devi lavorare su,diciamo,max un centianio di stringhe medio corte ok,sennò ti conviene guardarti qualche altro ordinamento(quick sort o heap sort:un po' +complessi da implementare ma sicuramente migliori in termini di complessità computazionale)

tutti dicono che il quick sort è meglio.... per me è peggio, soprattutto perchè, a contrario di quanto dici tu, crea problemi quando deve fare una grande quantità di scambi (certo, non a questi livelli di programmazione..) poichè è ricorsivo

[Insaponata]

il quick sort ha un tempo di esecuzione nel caso peggiore di n^2; però il caso medio se non ricordo male dovrebbe essere qualcosa intorno a n*log(n)... se la ricorsione funziona bene il quick sort è il migliore in assoluto (su numeri casuali).

cmq, detto per inciso, si può fare anche un quick sort non ricorsivo, ma l'algoritmo è un po' complicatuccio.

[janky]

sapresti procurartelo, o scriverlo? mi interesserebbe!