How can I change my following quick sort code so that I can use randomized pivot?

Question

How can I change my following quick sort code so that I can use randomized pivot instead of middle integer pivot?

public ArrayList<Integer> quicksort(ArrayList<Integer> input){

    if(input.size() <= 1){
        return input;
    }

    int middle = (int) Math.ceil((double)input.size() / 2);

    ##int randomint= arrayList.get(random.nextInt(arrayList.size()));##
    ##I WANT TO USE THIS RANDOMINT AS A PIVOT##

    int pivot = input.get(middle);

    ArrayList<Integer> less = new ArrayList<Integer>();
    ArrayList<Integer> greater = new ArrayList<Integer>();

    for (int i = 0; i < input.size(); i++) {
        if(input.get(i) <= pivot){
            if(i == middle){
                continue;
            }
            less.add(input.get(i));
        }
        else{
            greater.add(input.get(i));
        }
    }

    return concatenate(quicksort(less), pivot, quicksort(greater));
}

private ArrayList<Integer> concatenate(ArrayList<Integer> less, int pivot, ArrayList<Integer> greater){

    ArrayList<Integer> list = new ArrayList<Integer>();

    for (int i = 0; i < less.size(); i++) {
        list.add(less.get(i));
    }

    list.add(pivot);

    for (int i = 0; i < greater.size(); i++) {
        list.add(greater.get(i));
    }

    return list;
}

I want to use randomint as a pivot. When i try to substitute randomint directly, i get Array out of bound exception. Thanks.

Possible duplicate of [What causes a java.lang.ArrayIndexOutOfBoundsException and how do I prevent it?](http://stackoverflow.com/questions/5554734/what-causes-a-java-lang-arrayindexoutofboundsexception-and-how-do-i-prevent-it) — Deividi Cavarzan, Dec 02 '15 at 14:48
Your `randomint` is actually your pivot. `ArrayList.get()` returns the contents of the `ArrayList`. — Clark Kent, Dec 02 '15 at 14:51
Yes but when I try to use that "randomint" in the place of "middle" I get array out of bound exception — Riccado, Dec 02 '15 at 14:53
@riccado I have no idea what `arrayList` is in the line with the ##'s, but if it is what I think it is, then I believe it's because your ArrayList could be {40,60,80} -- Your `randomInt` would hold any one of those 3 numbers. Then you would attempt to get from your `input` at position 60, but it only has 3 elements, hence the `ArrayIndexOutOfBoundsException`. — Clark Kent, Dec 02 '15 at 14:55
@SaviourSelf so how can I change input.get to get the real position not the value? And arrayList is the object of java.util.ArrayList; — Riccado, Dec 02 '15 at 14:59
@riccado Right, but we don't see the definition of `arrayList` or anywhere else that it is used. Why is it here? Shouldn't it be `input` instead? — Clark Kent, Dec 02 '15 at 15:06
Yes, it should be input. I was confused. Thanks for ur help bro. — Riccado, Dec 02 '15 at 15:13

score 0 · Accepted Answer · answered Dec 02 '15 at 15:03

If you change the following line:

int randomint= arrayList.get(random.nextInt(arrayList.size()));

to

int randomint= random.nextInt(input.size());
int pivot = input.get(randomint);

If my suspicions are correct, this should give you the random pivot you're looking for.

How can I change my following quick sort code so that I can use randomized pivot?

1 Answers1