Pagina 1 di 1

[Algoritmi] Ordinamento array multipli di 2

MessaggioInviato: 12/07/2019, 11:54
da #Fede
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:

Codice:
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

Re: [Algoritmi] Ordinamento array multipli di 2

MessaggioInviato: 12/07/2019, 16:08
da vict85
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.

Re: [Algoritmi] Ordinamento array multipli di 2

MessaggioInviato: 12/07/2019, 16:12
da #Fede
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).

[Algoritmi, C] Re: [Algoritmi] Ordinamento array multipli di 2

MessaggioInviato: 12/07/2019, 16:23
da vict85
Il linguaggio è C?

Supponendo lo sia, il tuo confronto può essere semplificato:
Codice:
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;
}

Re: [Algoritmi] Ordinamento array multipli di 2

MessaggioInviato: 12/07/2019, 16:33
da #Fede
si

Re: [Algoritmi] Ordinamento array multipli di 2

MessaggioInviato: 12/07/2019, 16:46
da vict85
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ì
Codice:
    int moda = !(va % 2);
    int modb = !(vb % 2);

e invertendo l'ultimo return
Codice:
    // altrimenti distingui per gruppo
    // N.B.: moda < modb se a non e' il multiplo di 2
    return modb - moda;

Re: [Algoritmi] Ordinamento array multipli di 2

MessaggioInviato: 12/07/2019, 17:31
da #Fede
Grazie, ho pensato di modificare il modulo nel caso di numeri negativi in questo modo

Codice:
mod1 = abs(val1%2);
mod2 = abs(val2%2);


ed effettuare quindi il confronto così:

Codice:
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?

Re: [Algoritmi] Ordinamento array multipli di 2

MessaggioInviato: 13/07/2019, 11:55
da vict85
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?