0

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

//--EDIT--
//printField method

public static void printField (int[] field)
        {
            for(int i = 0; i<field.length; i++)
            {
                System.out.print(""+field[i]);
                if(i!=field.length-1)
                {
                    System.out.print(", ");
                }
                else
                {
                    System.out.print(";");
                }
            }
    }

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

Molly

Edit:
1)This is the exception I get: Exception
2)In the code quotation there is now my implementation of the method printField()

mollycodes
  • 11
  • 3
  • 1
    What exception do you get? (Please edit your answer) – SilverNak Apr 16 '17 at 15:12
  • The StackOverflow likely has nothing to do with the pivot selection. Your recursion is getting out of hand and looping forever. Evidently, left is always less than right. – Carcigenicate Apr 16 '17 at 15:13
  • If you get an exception in the method `printField`, then the implementation of that method is the code you should show us. – Philipp Apr 16 '17 at 15:16
  • 2
    Another issue is I don't think you are selecting your random pivot correctly. You want to pick a random pivot that is between left and right. As you start to recurse you don't want to pick pivots from the entire array, just the subcomponent of the array that is being worked on between left and right. – mba12 Apr 16 '17 at 15:19
  • @ErwinBolwidt Not every question which just mentions a stackoverflow error is a duplicate of that question. – Philipp Apr 16 '17 at 15:21
  • @Philip True, not every question. It wouldn't be an appropriate duplicate for a well-researched question that asked for something specific about StackOverflowErrors that isn't covered in that duplicate. But that's not the case here. It is an appropriate duplicate though for a question that could have used Google to start with and would otherwise be off-topic because it doesn't include the error, a specific question, the code to reproduce the error, etc. This is just like the duplicates we have for poor NullPointer related questions. – Erwin Bolwidt Apr 16 '17 at 15:42
  • @ErwinBolwidt If you dislike the question you should downvote it, not close it under a pretext. **If** you want it closed for being unclear, at least do that with the correct close-reason "unclear what you are asking". Closing it as a duplicate when it isn't is abuse of your gold-badge. – Philipp Apr 16 '17 at 16:11
  • Sorry if I somehow duplicated that other question about the stackoverflow exception and for being unclear. How could I make my question clearer for you to understand? I also researched here on stackoverflow and google to get an answer to my problem, because I believed my problem was in the use of Random or Math, but I just got something about Java Heap implementation.And I've just registered to stackoverflow, so I still need some time to understand how everything works here. However already thank you everyone for the hints! I just edited the ask. – mollycodes Apr 16 '17 at 16:15
  • Why do you not stop recursing when your partitions get small? It is common to use a different, linear, sort with short partitions. I am sure you can easily sort a partition with 1 or 2 members. Doing that also helps reduce the depth of recursion you need. – rossum Apr 16 '17 at 17:28

0 Answers0