[Algoritmi] Ordinamento array multipli di 2

Messaggioda #Fede » 12/07/2019, 11:54

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
#Fede
Starting Member
Starting Member
 
Messaggio: 16 di 20
Iscritto il: 20/04/2017, 15:33

Re: [Algoritmi] Ordinamento array multipli di 2

Messaggioda vict85 » 12/07/2019, 16:08

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.
vict85
Moderatore
Moderatore
 
Messaggio: 9760 di 9972
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: [Algoritmi] Ordinamento array multipli di 2

Messaggioda #Fede » 12/07/2019, 16:12

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).
#Fede
Starting Member
Starting Member
 
Messaggio: 17 di 20
Iscritto il: 20/04/2017, 15:33

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

Messaggioda vict85 » 12/07/2019, 16:23

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;
}
Ultima modifica di vict85 il 12/07/2019, 16:40, modificato 1 volta in totale.
vict85
Moderatore
Moderatore
 
Messaggio: 9761 di 9972
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: [Algoritmi] Ordinamento array multipli di 2

Messaggioda #Fede » 12/07/2019, 16:33

si
#Fede
Starting Member
Starting Member
 
Messaggio: 18 di 20
Iscritto il: 20/04/2017, 15:33

Re: [Algoritmi] Ordinamento array multipli di 2

Messaggioda vict85 » 12/07/2019, 16:46

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;
vict85
Moderatore
Moderatore
 
Messaggio: 9762 di 9972
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: [Algoritmi] Ordinamento array multipli di 2

Messaggioda #Fede » 12/07/2019, 17:31

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?
#Fede
Starting Member
Starting Member
 
Messaggio: 19 di 20
Iscritto il: 20/04/2017, 15:33

Re: [Algoritmi] Ordinamento array multipli di 2

Messaggioda vict85 » 13/07/2019, 11:55

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?
vict85
Moderatore
Moderatore
 
Messaggio: 9763 di 9972
Iscritto il: 16/01/2008, 00:13
Località: Berlin


Torna a Informatica

Chi c’è in linea

Visitano il forum: Raptorista e 5 ospiti