2

Estou tentando implementar o método quicksort, mas o código que escrevi não está funcionando, alguém pode me ajudar (ele ordena parte da sequência, mas alguns elementos continuam desordenados).

public static void quick(int v[], int start, int end) {

    if (end>start) {

        int pivo = v[(start+end)/2];

        int i = start;

        int f = end;

        while (f>i) {

            while (i <= end && v[i] < pivo) i++;
            while (f >= start && v[f] >= pivo) f--;

            if (f>i) {
                int aux = v[f];
                v[f] = v[i];
                v[i] = aux;
                i++;
                f--;
            }

        }
        if (f!= end)
            quick(v, start, f);
        if (i!=start)
            quick(v, i, end);
    }

}
1
  • pelo que eu consigo perceber, a ordenação não ocorre da forma esperada quando o pivô faz parte da sequência. mudei a estratégia do pivô, de elemento do meio para a metade dos extremos, e, agora, as vezes funciona e as vezes não. Commented 13/07/2016 às 14:50

2 Respostas 2

1

Algumas condições estava erradas, tenta:

 public static void quick(int v[], int start, int end) {
    int pivo = v[end + (start - end) / 2];
    int i = start;
    int f = end;
    while (i <= f) {
        while ( v[i] < pivo) {
            i++;
        }
        while (v[f] > pivo) {
            f--;
        }
        if (f >= i) {
            int aux = v[i];
            v[i] = v[f];
            v[f] = aux;
            i++;
            f--;
        }
    }
    if (start < f) {
        quick(v, start, f);
    }
    if (i < end) {
        quick(v, i, end);
    }

}
5
  • end + ( (start - end) / 2 ) = ( (2 * end) / 2 ) + ( ( start - end) / 2 ) = ( (2 * end + start - end) / 2 ) = (start + end) / 2
    – lpacheco
    Commented 13/07/2016 às 17:01
  • mas a estratégia para escolher o pivô pode ser qualquer uma nessa implementação. eu acho que o erro está acontecendo quando o pivo faz parte da sequencia. Commented 13/07/2016 às 17:33
  • Eu testei aqui e deu certo. Commented 13/07/2016 às 17:39
  • testa algumas vezes com números aleatórios, como eu disse, as vezes dá certo, as vezes não. o que quer dizer que está errado. Commented 13/07/2016 às 17:47
  • Por coincidência os valores que tinha testado estavam dando certo, mais creio que agora ta certo. Commented 13/07/2016 às 18:25
0

Acredito que a seguinte alteração funcione de forma adequada. O problema maior foi nas suas comparações (< ou >) onde deveria ser (<= ou >=) e vice-versa.

Coloquei alguns comentarios no código pra tentar ajudar a entender as alterações.

public static void quick(int v[], int start, int end) {

    //if (end>start) { //nao é necessária essa verificação aqui ... melhor testar se end > start na hora da recursao ... ELA ESTA CORRETA ... apenas mudei pq acho mais fácil entender assim

        int pivo = v[(start+end)/2];

        int i = start;

        int f = end;
        //particionamento
        while (f>=i) { //>= pq precisa entrar no if ...

            while (v[i] < pivo) i++; //removido teste "i <= end" (se o pivô esta dentro do intervalo start end pq verificar i <= end ?)
            while (v[f] > pivo) f--; //removido teste "f >= start" (mesmo motivo de "i <= end") ... removido o igual da comparação "v[f] >= pivô" para garantir que f não saia do intervalo [start, end]

            if (f>=i) { //aqui precisa menor *igual* pois o i e o f precisam ser incrementados mesmo que i == f! 
                int aux = v[f];
                v[f] = v[i];
                v[i] = aux;
                i++;
                f--;
            }

        }
        //recursao
        if (start < f)
            quick(v, start, f);
        if (i < end)
            quick(v, i, end);
    //}

}

Deixo pra voce, como exercício, simular o algoritmo para entender o motivo do seu código obter resultado errado.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .