DaGiraft - 1 year ago 59

Java Question

So here is the source code for my project. The

`"cmp(i,j)"`

`i < j`

`i > j`

`0`

`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);"`

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;

System.out.println(pivot);

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