Quicksort in Java does not work

Question

Quicksort in Java does not work

Navigation

#1 by (0 votes)
#2 by (0 votes)

1

I'm trying to implement the quicksort method, but the code I wrote is not working, someone can help me (it sorts part of the sequence, but some elements are still cluttered).

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);
    }

}

java quicksort

asked by anonymous 13.07.2016 / 16:31

2 answers

Error and Warning when changing platform from AnyCPU to x64 how to validate a quantity of columns from a csv file in php?

score 0 · Answer 1

I believe the following change works properly. The biggest problem was in your comparisons (< or >) where it should be (< = or > =) and vice versa.

I've put some comments in the code to try to help you understand the changes.

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);
    //}

}

I leave you, as an exercise, to simulate the algorithm to understand why your code gets the wrong result.

score 0 · Answer 2

Some conditions were wrong, try:

 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);
    }

}