[C++] Ordinare coordinate vettore
Buonasera a tutti.
Torno a scrivere per un questione ancora elementare. C'è qualcosa che non va nel codice, qualcosa che fa funzionare bene il programma per alcuni casi e non per altri.
La traccia chiede semplicemente di inserire un array (vettore) di $n$ componenti e stampare il vettore con le stesse componenti ma ordinate dalla minore alla maggiore (es: $(4,2,2,3)\quad =>\quad(2,2,3,4)$).
La strategia è stata la seguente: se ho [tex]$v=(a_1,a_2,a_3,...,a_n)$[/tex] stabilisco il minimo tra tutti e lo piazzo al primo posto con una sostituzione (chiamando la variabile ausiliaria etc).
Poi considero le componenti dalla seconda (la prima è il minimo tra tutte e l'ho già parcheggiata) alla -nesima (compresa quella che prima stava al posto1), trovo il minimo e metto al posto 2.
Iterando ho finito.
Il codice è questo (mi limito alla funzione)
Ad esempio se inserisco il vettore [tex]$(3,4,3,4)$[/tex] mi restituisce il vettore identico, senza alterazioni.
Mentre per altri vettore come [tex]$(4,4,4,2)$[/tex] o [tex]$(3,2,2,1)$[/tex] è ok.
Sembra che gli vada bene quando sono ordinati in maniera decrescente (allora me li mette crescenti, come da traccia).
Temo che la questione riguardai la faccenda del passaggio per indirizzo, non a caso ho messo la famosa & al vettore.
Avevo provato a mettere & anche prima di "min", 6 riga, ma è peggio, perchè come è giusto mi restituisce $(1,1,1,1)$ se metto
$(2,3,3,1)$.
Commenti vari sono graditi.
Mi scuso per la probabile banalità della cosa, e grazie in anticipo!
Torno a scrivere per un questione ancora elementare. C'è qualcosa che non va nel codice, qualcosa che fa funzionare bene il programma per alcuni casi e non per altri.
La traccia chiede semplicemente di inserire un array (vettore) di $n$ componenti e stampare il vettore con le stesse componenti ma ordinate dalla minore alla maggiore (es: $(4,2,2,3)\quad =>\quad(2,2,3,4)$).
La strategia è stata la seguente: se ho [tex]$v=(a_1,a_2,a_3,...,a_n)$[/tex] stabilisco il minimo tra tutti e lo piazzo al primo posto con una sostituzione (chiamando la variabile ausiliaria etc).
Poi considero le componenti dalla seconda (la prima è il minimo tra tutte e l'ho già parcheggiata) alla -nesima (compresa quella che prima stava al posto1), trovo il minimo e metto al posto 2.
Iterando ho finito.
Il codice è questo (mi limito alla funzione)
void ordinavett(vettore &v, int n)
{
float aux;
for (int h=0; h<n; h++)
{
float min=v[h]; int b=h;
for (int k=h+1; k<n; k++)
{
if(v[k]<min)
{min=v[k];
b=k;}
aux=v[h];
v[h]=v[b];
v[b]=aux;
}
}
for(int l=0; l<n; l++)
cout<<v[l]<<" ";
return;Ad esempio se inserisco il vettore [tex]$(3,4,3,4)$[/tex] mi restituisce il vettore identico, senza alterazioni.
Mentre per altri vettore come [tex]$(4,4,4,2)$[/tex] o [tex]$(3,2,2,1)$[/tex] è ok.
Sembra che gli vada bene quando sono ordinati in maniera decrescente (allora me li mette crescenti, come da traccia).
Temo che la questione riguardai la faccenda del passaggio per indirizzo, non a caso ho messo la famosa & al vettore.
Avevo provato a mettere & anche prima di "min", 6 riga, ma è peggio, perchè come è giusto mi restituisce $(1,1,1,1)$ se metto
$(2,3,3,1)$.
Commenti vari sono graditi.
Mi scuso per la probabile banalità della cosa, e grazie in anticipo!
Risposte
Conosco pochissimo il C, pertanto vado piu' per intuito che per conoscenze vere.
Mi sembra che il gruppo di istruzioni:
devono essere eseguite esterne al ciclo.
Ovvero te prima devi conoscere quale è il numero piu piccolo (ciclo del k) e poi, solo a fine ciclo eseguire la sostituzione.
Mi sembra che il gruppo di istruzioni:
aux=v[h]; v[h]=v[b]; v[b]=aux;
devono essere eseguite esterne al ciclo.
Ovvero te prima devi conoscere quale è il numero piu piccolo (ciclo del k) e poi, solo a fine ciclo eseguire la sostituzione.
I vettori non sono altro che puntatori al primo elemento dell'array con qualche limitazione. Non è necessario un typedef e l'uso dei reference per passare un vettore. Quando un vettore viene passato ad una funzione (SE QUESTO NON VIENE PASSATO PER REFERENCE) diventa un semplice puntatore. Se viene passato come reference allora è un reference ad un array e quindi in questo caso hai una specie di puntatore a puntatore. Ok, forse non è molto chiaro... Ti consiglio di prendere il tuo testo di riferimento e leggerti il capitolo che tratta questi argomenti con attenzione visto che non ti sono ancora del tutto chiari.
Per quanto riguarda l'algoritmo... Perché fai lo scambio all'interno del ciclo interno? In questo modo continui a scambiare il minimo temporaneo con l'elemento che era in h. Il metodo corretto è quello di scambiare gli elementi alla fine del ciclo esterno:
Comunque è probabilmente il metodo peggiore di ordinamento che si possa pensare (si chiama selection sort), anche se non il più semplice. Ti invito anche solo a dare un occhiata ai seguenti algoritmi di ordinamento (su un libro di algoritmi o anche su wikipedia - inglese - se non ne hai uno): insertion sort (molto semplice e con complessità O(n^2) nel caso peggiore ma per array quasi ordinati è efficientissimo), quicksort (l'algoritmo più amato e meno compreso probabilmente...), merge sort (complessità O(n*log(n))), heapsort (complessità O(n*log(n)) e infine il radix sort (complessità O(n)).
Per quanto riguarda l'algoritmo... Perché fai lo scambio all'interno del ciclo interno? In questo modo continui a scambiare il minimo temporaneo con l'elemento che era in h. Il metodo corretto è quello di scambiare gli elementi alla fine del ciclo esterno:
void ordinavett(float *v, int n)
{
for (int i = 0; i < n; ++i) {
float min = v[i];
int ind_min = i;
for (j = i+1; j < n; ++j) {
if (v[j] < min) {
min = v[j];
ind_min = j;
}
}
v[ind_min] = v[i];
v[i] = min; // non hai bisogno di una variabile aggiuntiva perché v[ind_min] == min...
}
}
Comunque è probabilmente il metodo peggiore di ordinamento che si possa pensare (si chiama selection sort), anche se non il più semplice. Ti invito anche solo a dare un occhiata ai seguenti algoritmi di ordinamento (su un libro di algoritmi o anche su wikipedia - inglese - se non ne hai uno): insertion sort (molto semplice e con complessità O(n^2) nel caso peggiore ma per array quasi ordinati è efficientissimo), quicksort (l'algoritmo più amato e meno compreso probabilmente...), merge sort (complessità O(n*log(n))), heapsort (complessità O(n*log(n)) e infine il radix sort (complessità O(n)).
Ciao; grazie mille ad entrambi.
Ok, dopo la vostra segnalazione mi sono convinto abbastanza in fretta perché sbagliavo. Ora gira, in effetti.
No, infatti non molto.
Fondamentalmente il corso che sto seguento (di 1° anno) rientra in "MAT/08 Analisi numerica", dove si dà una base di programmazione per poi lavorare su semplici problemi analitici (secanti, sistemi lineari, bisezione etc.).
Penso che si entrarà più nello specifico nel corso del semestre prossimo prettamente informatico, appunto Informatica Generale
Anche la dispensa da cui ho studiato è abbastanza minimale
Anche in italiano, in realtà
http://it.wikipedia.org/wiki/Algoritmo_ ... rdinamento
Fondamentalmente l'unico che poteva venirmi in mente oltre questo è l'insertion sort. Gli altri, temo di no.
Grazie per il consiglio comunque, ho letto volentieri.
Ora non mi vengono altre domande.
Grazie ancora per l'interessamento, a presto.
Ok, dopo la vostra segnalazione mi sono convinto abbastanza in fretta perché sbagliavo. Ora gira, in effetti.
Ok, forse non è molto chiaro... Ti consiglio di prendere il tuo testo di riferimento e leggerti il capitolo che tratta questi argomenti con attenzione visto che non ti sono ancora del tutto chiari.
No, infatti non molto.
Fondamentalmente il corso che sto seguento (di 1° anno) rientra in "MAT/08 Analisi numerica", dove si dà una base di programmazione per poi lavorare su semplici problemi analitici (secanti, sistemi lineari, bisezione etc.).
Penso che si entrarà più nello specifico nel corso del semestre prossimo prettamente informatico, appunto Informatica Generale
Anche la dispensa da cui ho studiato è abbastanza minimale
Ti invito anche solo a dare un occhiata ai seguenti algoritmi di ordinamento (su un libro di algoritmi o anche su wikipedia - inglese - se non ne hai uno):
Anche in italiano, in realtà
http://it.wikipedia.org/wiki/Algoritmo_ ... rdinamento
Fondamentalmente l'unico che poteva venirmi in mente oltre questo è l'insertion sort. Gli altri, temo di no.
Grazie per il consiglio comunque, ho letto volentieri.
Ora non mi vengono altre domande.
Grazie ancora per l'interessamento, a presto.
Credo sinceramente che sarebbe stato meglio se avessero fatto quei due corsi al contrario, prima quello di programmazione, in cui tra l'altro si imparava a calcolare la complessità degli algoritmi e a programmare, e poi quello di analisi numerica in cui si insegnano degli algoritmi specifici. 
Se non hai un testo da cui partire di consiglierei Thinking in C++ che è gratuito e fatto abbastanza bene, in attesa del libro che ti consiglieranno per il corso di programmazione.
Se non hai un testo da cui partire di consiglierei Thinking in C++ che è gratuito e fatto abbastanza bene, in attesa del libro che ti consiglieranno per il corso di programmazione.
Sì, non è la prima volta che vedo questo testo consigliato.
Terrò conto dell'indicazione, grazie ancora.
ps: il corso di Informatica già presuppone che si conoscano le basi della programmazione, date appunto da questo corso di Analisi numerica (Laboratorio di programmazione e calcolo). Probabilmente sono io che ho sottovalutato la cosa e ho tralasciato di entrare nello specifico.
Ciao!
Terrò conto dell'indicazione, grazie ancora.
ps: il corso di Informatica già presuppone che si conoscano le basi della programmazione, date appunto da questo corso di Analisi numerica (Laboratorio di programmazione e calcolo). Probabilmente sono io che ho sottovalutato la cosa e ho tralasciato di entrare nello specifico.
Ciao!
"Steven":
Ciao; grazie mille ad entrambi.
Ok, dopo la vostra segnalazione mi sono convinto abbastanza in fretta perché sbagliavo. Ora gira, in effetti.
Bene.
Volevo dirti, in ogni caso, che l'idea della sostituzione "simultanea" non era cattiva.
Ovvero, nel secondo ciclo (quello delle k), avresti potuto confrontare direttamente gli elementi v[h] con v[k] ed eventualmente sostituirli (senza utilizzare le variabili min e b).
Ciao 
Ok, infatti stavo provando a scribacchiare quest'idea così.
ma tuttavia in alcuni casi l'esito è sbagliato, come [tex]$(6,4,3)$[/tex] che restituisce [tex]$(3,6,4)$[/tex].
Ora in effetti non ho tempo per guardare meglio, ho provato a farmi a penna passo passo le operazioni del PC ma non ho trovato l'errore.
Un'altra cosa: questo procedimento (la sostituzione simultanea di Umby) è più conveniente di quello che alla fine ho fatto (selection sort)?
Infine: facendo il selection sort, avevo pensato nello stesso ciclo di agire da due parti.
Mi spiego: oltre a ordinare i vettori partendo da sinistra, e spingendo i minori a sinistra degli altri, contemporaneamente (anche nello stesso ciclo penso si possa fare) fare l'analogo a destra, ma ammucchiando a destra mano mano i maggiori.
In questo modo il programma deve "scorrere" meno volte la lista, ma ad ogni ciclo lavora un po' di più.
A conti fatti, pensate che una cosa simile convenga?
Grazie, e scusate la rottura prenatalizia.
Buone ferie a entrambi!
"Umby":
Ovvero, nel secondo ciclo (quello delle k), avresti potuto confrontare direttamente gli elementi v[h] con v[k] ed eventualmente sostituirli (senza utilizzare le variabili min e b).
Ok, infatti stavo provando a scribacchiare quest'idea così.
for (int h=0; h<n; h++)
{
for (int k=h+1; k<n; k++)
{
float aux;
if(v[k]<v[h])
{aux=v[h];
v[h]=v[k];
v[k]=aux;
}
}ma tuttavia in alcuni casi l'esito è sbagliato, come [tex]$(6,4,3)$[/tex] che restituisce [tex]$(3,6,4)$[/tex].
Ora in effetti non ho tempo per guardare meglio, ho provato a farmi a penna passo passo le operazioni del PC ma non ho trovato l'errore.
Un'altra cosa: questo procedimento (la sostituzione simultanea di Umby) è più conveniente di quello che alla fine ho fatto (selection sort)?
Infine: facendo il selection sort, avevo pensato nello stesso ciclo di agire da due parti.
Mi spiego: oltre a ordinare i vettori partendo da sinistra, e spingendo i minori a sinistra degli altri, contemporaneamente (anche nello stesso ciclo penso si possa fare) fare l'analogo a destra, ma ammucchiando a destra mano mano i maggiori.
In questo modo il programma deve "scorrere" meno volte la lista, ma ad ogni ciclo lavora un po' di più.
A conti fatti, pensate che una cosa simile convenga?
Grazie, e scusate la rottura prenatalizia.
Buone ferie a entrambi!
"Steven":
Un'altra cosa: questo procedimento (la sostituzione simultanea di Umby) è più conveniente di quello che alla fine ho fatto (selection sort)?
No, non lo è per niente. E' anzi probabilmente meno efficiente (oltre che più difficile da implementare...). Con il suo metodo infatti incrementi il numeto di scambi e mantieni costante il numero di confronti.
"Steven":
Infine: facendo il selection sort, avevo pensato nello stesso ciclo di agire da due parti.
Mi spiego: oltre a ordinare i vettori partendo da sinistra, e spingendo i minori a sinistra degli altri, contemporaneamente (anche nello stesso ciclo penso si possa fare) fare l'analogo a destra, ma ammucchiando a destra mano mano i maggiori.
In questo modo il programma deve "scorrere" meno volte la lista, ma ad ogni ciclo lavora un po' di più.
A conti fatti, pensate che una cosa simile convenga?
E' una variante conosciuta, anche se non porta ad alcun vantaggio in pratica. Lascia perdere l'insertion sort e passa ad altro...
"Steven":
ma tuttavia in alcuni casi l'esito è sbagliato, come [tex]$(6,4,3)$[/tex] che restituisce [tex]$(3,6,4)$[/tex].
Ora in effetti non ho tempo per guardare meglio, ho provato a farmi a penna passo passo le operazioni del PC ma non ho trovato l'errore.
Mi sembra che ci manchi una parentesi (ovvero quella che chiude l'if). Dimmi se è vero o meno...
"Steven":
Un'altra cosa: questo procedimento (la sostituzione simultanea di Umby) è più conveniente di quello che alla fine ho fatto (selection sort)?
C'e' un compromesso da tenere presente ed è:
Semplicità del codice <==> Efficienza
Spesso il codice piu' semplice è il meno efficiente, e viceversa.
Ora tutto dipende dalla grandezza della tabella. Il codice che hai usato è semplice e molto intuitivo e puoi tranquillamente usarlo per tabelle di piccole, medie dimensioni (in fondo si tratta di istruzioni elementari che vengono eseguite dalla CPU senza lettura / scrittura di archivi e quindi velocissime).
"Steven":
In questo modo il programma deve "scorrere" meno volte la lista, ma ad ogni ciclo lavora un po' di più.
Buone ferie a entrambi!
Si è vero... ad ogni ciclo di scorrimento ottieni due numeri ordinati. Il piu piccolo a sx, il piu grande a dx. Pero' nel ciclo devi inserire un doppio if, con un doppio trasferimento di dati. Pertanto alla fine il numero di istruzioni sarà piu o meno lo stesso (complicando notevolmente il codice [cosa che a me non piace])
Buone Feste a te ed a tutti gli utenti del forum.
"Umby":
C'e' un compromesso da tenere presente ed è:
Semplicità del codice <==> Efficienza
Spesso il codice piu' semplice è il meno efficiente, e viceversa.
Ora tutto dipende dalla grandezza della tabella. Il codice che hai usato è semplice e molto intuitivo e puoi tranquillamente usarlo per tabelle di piccole, medie dimensioni (in fondo si tratta di istruzioni elementari che vengono eseguite dalla CPU senza lettura / scrittura di archivi e quindi velocissime).
In questo caso però la tua idea non semplifica il codice (rende anzi più difficile seguire il flusso del programma perché l'array varia più spesso) e peggiora le performance di uno dei peggiori algoritmi esistenti per l'ordinamento di array. Esistono molti algoritmi semplici quanto il selection sort e che sono in pratica più efficienti. Per array piccoli e quasi ordinati si usa normalmente l'insertion sort (che è quasi lineare quando l'array è praticamente ordinato). In ogni caso...
Buon Natale a tutti!!!
"Umby":
Mi sembra che ci manchi una parentesi (ovvero quella che chiude l'if). Dimmi se è vero o meno...
A dire il vero l'if lo stavo chiudendo con la parentesi a capo, ma con la tua osservazione ho comunque risolto: il problema era che non chiudevo (una perentesi in meno c'era d'altronde!) l'elenco delle istruzioni del for, includendo quindi la successiva istruzione di stampa della componenti, che quindi non avveniva alla fine ma mano mano.
Grazie a entrambi per i pareri sull'efficienza.
A presto!
"Steven":
[quote="Umby"]Mi sembra che ci manchi una parentesi (ovvero quella che chiude l'if). Dimmi se è vero o meno...
A dire il vero l'if lo stavo chiudendo con la parentesi a capo, ma con la tua osservazione ho comunque risolto: il problema era che non chiudevo (una perentesi in meno c'era d'altronde!) l'elenco delle istruzioni del for, includendo quindi la successiva istruzione di stampa della componenti, che quindi non avveniva alla fine ma mano mano.
Grazie a entrambi per i pareri sull'efficienza.
A presto![/quote]
In effetti c'erano 3 condizioni (2 cicli "for" ed 1 "if"), con due chiusure di parentesi. Dire quale delle 3 ci mancava era difficile. Ti consiglierei di allineare l'apertura di una condizione con la chiusura della parentesi in modo tale chi legge il codice possa capire facilmente dove inizia la condizione e dove termina.
"apatriarca":
In questo caso però la tua idea non semplifica il codice .....
Non ho nessun dubbio che l'algoritmo non sia efficiente. Probabilmente qualsiasi altro algoritmo da te menzionato nel tuo intervento precedente è piu' efficiente di questo.
Ma quando parlo di semplicità del codice non mi riferisco al "flusso del programma e del fatto che l'array varia più spesso", ma al fatto che con sole due istruzioni (semplici da capire e molto intuitive) riesco ad ottenere il risultato. Che poi il computer debba lavorare di piu'(appunto per la inefficienza del codice) mi potrebbe interessare di meno.
Mi capita spesso di leggere programmi scritti da altri colleghi per correggere qualche errore o per implementarlo, e la cosa piu' difficile è "capire" come funziona il programma. Se non lo comprendi in fondo, non puoi fare alcuna modifica.
IMHO: meglio avere un programma semplice, lineare, pulito, chiaro, di facile lettura, anche se a svantaggio della velocita' di esecuzione.
"Umby":
[quote="apatriarca"]
In questo caso però la tua idea non semplifica il codice .....
Non ho nessun dubbio che l'algoritmo non sia efficiente. Probabilmente qualsiasi altro algoritmo da te menzionato nel tuo intervento precedente è piu' efficiente di questo.
Ma quando parlo di semplicità del codice non mi riferisco al "flusso del programma e del fatto che l'array varia più spesso", ma al fatto che con sole due istruzioni (semplici da capire e molto intuitive) riesco ad ottenere il risultato. Che poi il computer debba lavorare di piu'(appunto per la inefficienza del codice) mi potrebbe interessare di meno.
Mi capita spesso di leggere programmi scritti da altri colleghi per correggere qualche errore o per implementarlo, e la cosa piu' difficile è "capire" come funziona il programma. Se non lo comprendi in fondo, non puoi fare alcuna modifica.
IMHO: meglio avere un programma semplice, lineare, pulito, chiaro, di facile lettura, anche se a svantaggio della velocita' di esecuzione.
[/quote]Ma in questo caso il numero di istruzioni è praticamente identico, l'unica cosa che cambia è fare lo scambio fuori dal ciclo o dentro. E secondo me facendolo fuori dal ciclo si aumenta la sua chiarezza invece di diminuirla.
prima ti puoi creare una funzione che ti ordini il vettore:
poi dopo puoi cercare di ingegnarti creando una funzione che ti dia l'array al contrario....
void ordina(int V[N])
{
int temp;
for(int i = 0; i < N; i++)
for(j = 1; j < N; j++)
if(V[j - 1] > V[j])
temp = V[j - 1];
V[j - 1] = V[j];
V[j] = temp;
}
poi dopo puoi cercare di ingegnarti creando una funzione che ti dia l'array al contrario....
Non riesco a capire il senso del codice che hai postato. Il problema è già stato ampiamente risolto e la tua soluzione è inutilmente inefficiente. Perché infatti ordinare l'array al contrario di quello richiesto, per poi scambiare tutti gli elementi? Sarebbe stato infatti sufficiente cambiare il test all'interno della selezione, come già fatto nel codice originale, e ordinarlo nel modo corretto.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo