DaGiraft DaGiraft - 1 year ago 59
Java Question

Implementing the use of a random pivot instead of choosing the first element as pivot in QuickSort, java

So here is the source code for my project. The

function returns a negative value if
i < j
, a positive value if
i > j
, and
i = j

As you can see, I choose the current first element of the list as pivot, which works. Now I want to use a random pivot. If I just do a "
int pivot = first + random.nextInt(last-first+1);"
I get a ton of error on runtime.

Source code:

public void sort(){
sortQuick(0, getElementCount()-1);
public void sortQuick (int first, int last){
// pivot tilldelas ett värde mellan noll och antal element i vektorn.
//final Random random = new Random();
System.out.println(("Last: " + last + ", first : " + first));
//int pivot = first + random.nextInt(last-first+1);
int pivot = first;
int up = first; // index of left-to-right scan
int down = last; // index of right-to-left scan

if (last - first >= 1){ // check that there are at least two elements to sort

// set the pivot as the first element in the partition

while (down > up) { // while the scan indices from left and right have not met,

while (cmp(up,pivot) <= 0 && up <= last && down > up) // from the left, look for the first
up++; // element greater than the pivot
while (cmp(down,pivot) > 0 && down >= first && down >= up) // from the right, look for the first
down--; // element not greater than the pivot
if (down > up){ // if the left seekindex is still smaller than
swap(up, down);
// the right index, swap the corresponding elements
swap(first, down); // after the indices have crossed, swap the last element in
// the left partition with the pivot
sortQuick(first, down - 1); // quicksort the left partition
sortQuick(down + 1, last); // quicksort the right partition
else // if there is only one element in the partition, do not do any sorting
return; // the array is sorted, so exit

Answer Source

The problem is that when you do

int pivot = first + random.nextInt(last-first+1)

you doesn't check if last > first before. So, you can be in the case where last < first, and try to call random.nextInt() with a negative (or zero) parameter, which doesn't makes sense, and so you will get and IllegalArgumentException.

What you have to do, is to move the pivot calculation inside your if():

if (last - first >= 1){               // check that there are at least two elements to sort
    int pivot = first + random.nextInt(last-first+1);