parImpar

parImpar

por José Coelho de Pina -
Número de respostas: 8

Função parImpar recebe um inteiro n e um vetor v[0..n-1] de inteiros e retorna um índice k e rearranja o vetor v de modo que todos os números em v[0..k-1] são ímpares e todos os números em v[k..n-1] são pares. O consumo de tempo é O( n) e o espaço extra é O(1).

void
parImpar(int n, int v[])
{
    /* espaco extra 3 x sizeof(int) == 12(?) bytes =  O(1) */
    int i; 
    int k;
    int t;

    k = 0;
    for (i = 0; /* A */ i < n; i++)
    {
        if (v[i] % 2 == 0) 
        {
            t    = v[k];
            v[k] = v[i];
            v[i] = t;
            k += 1;
        }
    }

    return k;
}

Em /* A */ vale que

números em v[0..k-1] são ímpares e
números em v[k..i-1] são pares

No início da última iteração i == n e a correção é evidente.

Em resposta à José Coelho de Pina

Re: parImpar

por José Coelho de Pina -

Comentários sobre a solução a seguir?

void
parImpar(int n, int v[])
{
    int i;
    int *w = malloc(n sizeof(int));
    int e, d;

    e = 0; d = n-1;
    for (i = 0; i < n; i++)
    {
        if (v[i] % 2 == 0)
        {
             w[e++] = v[i];
        }
        else
        {
             w[d--] = v[i];
        }
    }

    for (i = 0; i < n; i++)
    {
        v[i] = w[i];
    }

    free(w);

    return e;
}
Em resposta à José Coelho de Pina

Re: parImpar

por João Henrique Luciano -

Como a função aloca espaço auxiliar proporcional ao tamanho da entrada (no caso, o número inteiro n), a função tem espaço auxiliar O( n).

Em resposta à José Coelho de Pina

Re: parImpar

por José Coelho de Pina -

"bla % 2 == 1" é equivalente a "bla % 2 != 0"?

Em resposta à José Coelho de Pina

Re: parImpar

por Gustavo Estrela de Matos -

Acho que pode complicar quando você usa números negativos, não? Pode ser que um número ímpar tenha resto -1?

Em resposta à Gustavo Estrela de Matos

Re: parImpar

por Gustavo Chicato -

Sim, pois em C operador % com dividendo negativo devolve resultado negativo. Logo (-3) % 2 == -1, por exemplo.

Assim, há um problema em usar a condição "bla % 2 == 1", já que ela só funciona para números positivos.

Em resposta à Gustavo Chicato

Re: parImpar

por José Coelho de Pina -

Só complementando. Vejam o trecho que copie do livro do Kernighan and Ritchie:

  "...The binary / operator yields the quotient, and the % operator the remainder, of the division of the first operand by the second; if the second operand is 0, the result is undefined. Otherwise, it is always true that (a/b)*b + a%b is equal to a . If both operands are non-negative, then the remainder is non-negative and smaller than the divisor, if not, it is guaranteed only that the absolute value of the remainder is smaller than the absolute value of the divisor...."