[C++] Algoritmo di ordinamento

[Landau1]

Salve a tutti, ho una domanda sull'implementazione dell'algoritmo di ordinamento crescente di un vettore. Questo è il codice esplicito che ho utilizzato:

int posMin;
	
	for(unsigned int i=0; i<numero-1; i++){
		
		posMin=i;
		
		for(unsigned int j=i+1; j<numero; j++){
			if(v[j]<v[posMin]){
				posMin=j; 
			}
		}
		
		scambia(v[i],v[posMin]);
	}
		
	cout << "il vettore riordinato è: ";
		
	for(unsigned int i=0; i<numero; i++){
		cout << dati[i] << " ";
	}

Tuttavia ho da parte questa funzione, che determina la posizione del minimo di un vettore di dimensione determinata:

float trovaMin(float v[], dim){
	
	float min, posMin;
	v[0]=min;		
	for(unsigned int i=1; i<dim; i++){
		if(v[i]<min){
			v[i]=min;
			posMin=i;
		}		
	}

return posMin;

}

E' possibile riscrivere l'algoritmo di ordinamento utilizzando questa funzione? Finora i miei tentativi sono stati fallimentari purtroppo, e non capisco perché

[Super Squirrel]

Il primo codice che hai postato in linea di massima va bene, il secondo decisamente no:
- perchè ritorna un float?
- perchè assegni al primo elemento dell'array un valore pseudocasuale?
- per quello che è lo scopo della funzione la variabile min è superflua, basta solo posMin.

Immagino tu non abbia controllato la validità della funzione prima di utilizzarla. Peraltro una versione corretta della funzione è contenuta nel primo codice che hai postato.

[Landau1]

Ciao, grazie per la risposta. Ho corretto la funzione, ma ancora non riesco a capire come costruire l'algoritmo di ordinamento mettendo insieme trovaMin e scambia

Il ragionamento è semplice: considero il primo elemento, lo confronto con tutti quelli successivi finché trovo l'indice in cui sta quello più piccolo in assoluto; dopodiché scambio il primo elemento con quest'ultimo. Itero il procedimento partendo dal secondo ed esaminando solo quelli dal terzo in poi, e così via. Il problema è che trovaMin agisce su tutto il vettore e non so come farlo agire solo su una parte...

[Super Squirrel]

Perchè non posti quello che hai scritto finora?

Il problema è che trovaMin agisce su tutto il vettore e non so come farlo agire solo su una parte...

Basta passargli anche l'indice da cui iniziare a scorrere l'array.

[Landau1]

Quindi in pratica scrivere così (non ho tolto la variabile min, chiedo venia):

int trovaMin(float v[], dim, i){
	
	float min, posMin;
	min=v[0];		
	for(unsigned int j=i+1; i<dim; i++){
		if(v[i]<min){
			v[i]=min;
			posMin=i;
		}		
	}

return posMin;

}

int posMin;
	
	for(unsigned int i=0; i<numero-1; i++){
		scambia(trovaMin(v, numero, i), v[i])
	}
}

[Super Squirrel]

Ci sono moltissime cose che non vanno bene ...

Innanzitutto perchè non posti l'intero codice del programma se l'hai scritto?
Il codice compila? In tal caso ne hai testato il funzionamento su un array?

[Landau1]

Allora credo di aver interpretato male il suggerimento Comunque questo è il codice completo e sistemato: manca ovviamente il main che non sono capace di finire...

#include <iostream>
#include <cmath>

#define N 10

using namespace std;

void scambia(float, float);
float trovaMin(float[], dim);

int main(){

	float array[N];
	for(unsigned int i=0; i<N; i++){
		cout << "Inserire componente " i "-esima: ";
		cin >> array[i];
	}
        return 0;
}

void scambia (float a, float b){

	float tmp=0;
	tmp=a;
	a=b;
	b=tmp;
}

int trovaMin(float v[], dim){
	
	float posMin;
	posMin=0;		
	for(unsigned int i=0; i<dim; i++){
		if(v[i]<v[posMin]){
			posMin=i;
		}		
	}

	return posMin;
}

[yankarinRG]

Il codice è ancora pieno di errori, tra cui: return type tra dichiarazione e definizione non uguale, mancanza di "<<" tra "i" (sulla stampa del componente i-esimo), libreria cmath mai utilizzata e le funzioni scambia e trovaMin le hai implementate, ma mai utilizzate. Con qualche piccola modifica funziona. Ti ho commentato le parti "incriminate"

#include <iostream> //sotto c'era cmath, non necessaria

#define N 10

using namespace std;

void scambia(float, float);
int trovaMin(float [], int); // anziché del tipo int c'era dim

int main(){

   float array[N];
   for(unsigned int i=0; i<N; i++){
      cout << "Inserire componente " << i << "-esima: "; // mancanza <<
      cin >> array[i];
   }
        return 0;
}

void scambia(float a, float b){

   float tmp=0;
   tmp=a;
   a=b;
   b=tmp;
}

int trovaMin(float v[], int dim){
   
   int posMin; // prima era float
   posMin=0;      
   for(unsigned int i=0; i<dim; i++){
      if(v[i]<v[posMin]){
         posMin=i;
      }      
   }

   return posMin;
}

[Landau1]

Ops, grazie per la sistemata... comunque ho implementato scambia e trovaMin per ordinare il vettore nel main, solo che non riesco a combinarle nel modo giusto. Per quello mancano!

P.S. Perdonate la noobbaggine, sono un programmatore novello

[Super Squirrel]

Per quanto riguarda l'ultimo codice che hai postato, oltre agli errori evidenziati da yankarinRG, farei qualche altra osservazione:
- il corpo della funzione scambia è corretto, ma la sua definizione è sbagliata. Conosci la differenza tra passaggio per valore e passaggio per riferimento?
- perchè nella funzione scambia inizializzi la variabile tmp a 0 e non direttamente ad "a"?
- nella funzione trovaMin, la prima iterazione del ciclo for è inutile perchè vai a confrontare il primo elemento con se stesso. In pratica puoi benissimamente inizializzare la variabile "i" a 1;
- se nei cicli for utilizzi il tipo unsigned int per gli indici dell'array, perchè non fai ritornare un unsigned int anche alla funzione trovaMin?


Per quanto riguarda la questione iniziale non credo tu sia tanto lontano dalla soluzione.

In precedenza hai postato

for(unsigned int i = 0; i < numero - 1; i++){
    scambia(trovaMin(v, numero, i), v[i])
}

e non è sbagliato, o almeno non del tutto. In pratica l'impostazione logica è corretta, ma c'è qualcosa che non va nello scambio... riesci a capire cosa?

Per quanto riguarda la funzione trovaMin, abbiamo già assodato che va modificata se vuoi riscrivere l'algoritmo di ordinamento utilizzando tale funzione. In precedenza hai postato:

int trovaMin(float v[], int dim, int i)
{
   //varie cose sbagliate...
   return posMin;
}

L'impostazione è corretta, sapresti aggiustare il corpo della funzione?

[Landau1]

"Super Squirrel":Conosci la differenza tra passaggio per valore e passaggio per riferimento?

Ho dato una ripassatina, e in effetti nella funzione scambia dovrei passare i parametri per riferimento in modo da modificare correttamente i parametri attuali del main:

void scambia (float &a, float &b){

	float tmp=0;
	tmp=a;
	a=b;
	b=tmp;
}

Per quanto riguarda le altre tre domande, la risposta giusta è, non ci avevo pensato.

Ho provato a riscrivere la funzione trovaMin passandole anche l'indice:

unsigned int trovaMin(float v[], int dim, unsigned int j){

	unsigned int posMin;
	posMin=j;
	for(unsigned int i=j+1; i<dim; i++){
		if(v[i]<v[posMin]){
			posMin=i;
		}		
	}
	return posMin;
}

Il problema con lo scambio invece non lo riesco a vedere

[Super Squirrel]

Bene, hai aggiustato quasi tutto!

Il problema con lo scambio invece non lo riesco a vedere

Con la seguente linea di codice

scambia(trovaMin(v, numero, i), v[i])

cosa stai scambiando?
Inoltre tale codice non compilerebbe nemmeno perchè la funzione scambia si aspetta due float, mentre tu gli stai passando un unsigned int e un float!

[Landau1]

Hai ragione, che svista. Dovrebbe essere scambia(v[trovaMin(v, numero, i)], v)...