Quicksort in Java does not work

Asked

Viewed 257 times

2

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 remain 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

  • From what I can tell, the ordering does not occur as expected when the pivot is part of the sequence. I changed the pivot strategy from the middle element to half the edges, and now it sometimes works and sometimes it doesn’t.

2 answers

1

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

}

  • end + ( (start - end) / 2 ) = ( (2 * end) / 2 ) + ( ( start - end) / 2 ) = ( (2 * end + start - end) / 2 ) = (start + end) / 2

  • but the strategy to choose the pivot can be anyone in that implementation. I think the error is happening when the pivot is part of the sequence.

  • I tested it here and it worked.

  • tests a few times with random numbers, as I said, sometimes it works, sometimes it doesn’t. which means it’s wrong.

  • By coincidence the values I had tested were working, but now I think it’s right.

0

I believe that the following amendment will work properly. The biggest problem was in their comparisons (< or >) where it should be (<= or >=) and vice versa.

I put some comments in the code to try to help 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 it to you, as an exercise, to simulate the algorithm to understand why your code gets wrong result.

Browser other questions tagged java quicksort

You are not signed in. Login or sign up in order to post.