Stackoverflow in Quick Sort

Question

I’m having a problem here at this meeting. These are functions for an array of objects using the Quick Sort algorithm, and I’m getting the Stackoverflow error, and I can’t identify the source. Someone help me 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;
    }
}

Answer 1

The problem is an infinite recursion. I’ll put the original code and then fix:

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

Did you see the difference? No? Well, she’s subtle.

Quicksort is defined in two parts:

1. quicksort, the recursive part
2. Partition, where it partitions according to a pivot value

In this case, quicksort is defined as 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 left until the pivot position and then another quicksort is called after the pivot position until right.

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

Behold that answer for more details about the error stackoverflow.