Stackoverflow in quick sort

Question

Stackoverflow in quick sort

Navigation

#1 by (3 votes)

2

I'm having a problem here in this code. These are functions for an array of objects using the quick sort algorithm, and I'm having the Stackoverflow error, and I can not identify the source. Someone help me to identify the source of the error?

 static Musica[] ordenarMusicosIdQuickSort(Musica[] musica){
        return ordenarMusicosIDQuickSort(musica, 0, musica.length);
    }

    static Musica[] ordenarMusicosIDQuickSort(Musica[] musica, int left, int right){
        if(left<right){
            int posicaoPivot = partition(musica, left, right-1);
            musica = ordenarMusicosIDQuickSort(musica, left, right);
            musica = ordenarMusicosIDQuickSort(musica, posicaoPivot + 1, right);
        }
        return musica;
    }

    static int partitionID(Musica[] musica, int left, int right){
        Musica pivot=musica[right];
        int startR=left-1;

        for(int endR=left; endR<right; endR++){
            if(musica[endR].id_interprete>pivot.id_interprete){
                startR++;
                Musica temp=musica[endR];
                musica[endR]=musica[startR];
                musica[startR]=temp;
            }

        }
        Musica temp=musica[right];
        musica[right]=musica[startR+1];
        musica[startR+1]=temp;

        return startR+1;
    }
}

java quicksort

asked by anonymous 06.07.2017 / 01:40

1 answer

Problems in capturing input when opening modal How to leave a negative number in php?

score 3 · Accepted Answer

The problem is in an infinite recursion. I go by the original code and then the correction:

static Musica[] ordenarMusicosIDQuickSort(Musica[] musica, int left, int right){
        if(left<right){
            int posicaoPivot = partition(musica, left, right-1);
            musica = ordenarMusicosIDQuickSort(musica, left, right);
            musica = ordenarMusicosIDQuickSort(musica, posicaoPivot + 1, right);
        }
        return musica;
    }

Correction:

static Musica[] ordenarMusicosIDQuickSort(Musica[] musica, int left, int right){
        if(left<right){
            int posicaoPivot = partition(musica, left, right-1);
            musica = ordenarMusicosIDQuickSort(musica, left, posicaoPivot);
            musica = ordenarMusicosIDQuickSort(musica, posicaoPivot + 1, right);
        }
        return musica;
}

Have you seen the difference? Not? Well, it's subtle.

Quicksort is defined in two parts:

quicksort, the recursive part

partition, where partitioning according to a pivot value

In the case, quicksort is defined thus in pseudo code:

quicksort(left, right):
    if left < right:
        posPivot = partition(left, right)
        quicksort(left, posPivot)
        quicksort(posPivot + 1, right)

Note that after partitioning, it is called quicksort from left to the position of the pivot, and then another quicksort is called after the position of the pivot to right .

In the original code, the first recursive call was not from left to pivot position, but from left to right .

See this answer for more details on the stackoverflow error.