dimanche 16 avril 2017

Java - Quicksort random pivot leads to stackoverflow exception [duplicate]

This question already has an answer here:

Hello Stackoverflow community,

I'm doing an assignment for my algorithm class.
We should implement a quicksort algorithm which uses as pivot a random element of the array.
I tried to implement this with Random and Math, but in both cases I get an exception when I'm trying to print the field in the method printField.
Where am I doing something wrong? I'm guessing I am having a problem with the recursive use of the method, but I don't know.

This is my code:



public static void quickSort(int[] field, int left, int right)
{        
    if (field== null || field.length == 0)
        return;

    if (left >= right)
        return;

        // pick the pivot
        int middle = left + (right - left) / 2;
        int pivot;
        if(field.length>1){
        pivot = ((int) Math.random()) % field.length;
        pivot = field[pivot];}
        else
        {
            pivot = field[0];
        }
        //int pivot = field[middle];

        // make left < pivot and right > pivot
        int i = left, j = right;
        while (i <= j) {
            while (field[i] < pivot) {
                i++;
            }

            while (field[j] > pivot) {
                j--;
            }

            if (i <= j) {
                int temp = field[i];
                field[i] = field[j];
                field[j] = temp;
                i++;
                j--;
            }

            printField(field);
            System.out.println("");
        }

        // recursively sort two sub parts
        if (left < j)
            quickSort(field, left, j);

        if (right > i)
            quickSort(field, i, right);

}

Thank you already for your help!
Have a nice day!

Molly




Aucun commentaire:

Enregistrer un commentaire