[Algoritmi] Ordinamento array multipli di 2
Buongiorno ragazzi, ho il seguente problema:
scrivere un algoritmo in loco che ordini un vettore di interi in modo da ottenere il seguente effetto: l'array ordinato deve contenere prima tutti i multipli di 2 e a seguire tutti quelli che non lo sono.
La mia idea è quella di utilizzare la funzione qsort per il confronto nel seguente modo:
che ne dite?
Grazie
scrivere un algoritmo in loco che ordini un vettore di interi in modo da ottenere il seguente effetto: l'array ordinato deve contenere prima tutti i multipli di 2 e a seguire tutti quelli che non lo sono.
La mia idea è quella di utilizzare la funzione qsort per il confronto nel seguente modo:
int confronta(const void *a, const void *b){ int val1, val2, mod1, mod2; val1 = *((int*)a); val2 = *((int*)b); mod1 = (va1%2); mod2 = (va2%2); if ( (mod1== 0) && (mod2 == 0)) //sono entrambi multipli return val1-val2; else if ( (mod1!= 0) && (mod2 != 0) ) //sono entrambi non multipli return val1-val2; else if ( (mod1== 0) && (mod2!=0) ) //mod1 è multiplo di 2, mod2 non è multiplo di 2 return val1-val2; else //mod2 è multiplo di 2, mod1 non è multiplo di 2 return val2-val1; } void qsort(void *a, n, sizeof(a[0]), confronta);
che ne dite?
Grazie
Risposte
Ti fai confondere dal fatto che parla di un ordinamento. Ma in realtà si tratta di una partizione. Vuoi mettere tutti i multipli di due all'inizio e alla fine quelli che non lo sono. Si può fare con un singolo passaggio sull'array. Se ti chiede anche che i due sottoarray siano ordinati allora il testo non è molto chiaro.
Mi scuso se il testo non è molto chiaro. La richiesta dell'esercizio è che l'array deve contenere prima tutti i multipli di 2 (in ordine crescente) e a seguire tutti quelli che non lo sono (sempre in ordine crescente).
Il linguaggio è C?
Supponendo lo sia, il tuo confronto può essere semplificato:
Supponendo lo sia, il tuo confronto può essere semplificato:
int confronta( const void* a, const void* b ) { int va = *(int*)a; int vb = *(int*)b; int moda = va % 2; int modb = vb % 2; // se sono entrambi nello stesso gruppo if ( moda == modb ) { return va - vb; } // altrimenti distingui per gruppo // N.B.: moda < modb se a e' il multiplo di 2 return moda - modb; }
si
Ho aggiornato il messaggio di prima anche se non sono sicuro che il modulo funzioni bene nel caso in cui si abbia a che fare con numeri negativi. Probabilmente conviene cambiare i moduli così
e invertendo l'ultimo return
int moda = !(va % 2); int modb = !(vb % 2);
e invertendo l'ultimo return
// altrimenti distingui per gruppo // N.B.: moda < modb se a non e' il multiplo di 2 return modb - moda;
Grazie, ho pensato di modificare il modulo nel caso di numeri negativi in questo modo
ed effettuare quindi il confronto così:
corretto?
mod1 = abs(val1%2); mod2 = abs(val2%2);
ed effettuare quindi il confronto così:
int confronta(const void *a, const void *b){ int val1, val2, mod1, mod2; val1 = (*(int*)a); val2 = (*(int*)b); mod1 = abs(val1 % 2); mod2 = abs(val2 % 2); if(mod1 == mod2){ return val1 -val2; } else if(mod1 == 0){ return val1-val2; }else return mod1-mod2; }
corretto?
Ho già scritto come puoi gestire la cosa. Il modulo può assumere al massimo 3 valori: 0, 1, -1. Gli ultimi due sono equivalenti. Quindi ti basta modificare il calcolo del modulo con il test che sia o meno uguale a 0. L'uso della negazione è più rapito ma probabilmente meno chiaro. Insomma val1%2==0 è un valore intero nel C (uguale a 0 se falso e 1 se vero).
L'else if non ha alcun senso. Perché pensi sia necessario?
L'else if non ha alcun senso. Perché pensi sia necessario?