kobe - 1 year ago 85

Java Question

I have the following code which is working fine , but can anybody tell me how to change the alogirithm to use random pivot element.

instead of below , i want to select pivot element randomly , any help will be appreciated

`int pivot = arr[(left + right) / 2];`

import java.util.Random;

public class QuickSort {

/**

* @param args

*/

public static void main(String[] args) {

int i;

int array[] = {10,9,1,2,3,4,100,200,300,400};

System.out.println(" Quick Sort\n\n");

System.out.println("Values Before the sort:\n");

for(i = 0; i < array.length; i++)

System.out.print( array[i]+" ");

System.out.println();

quickSort(array,0,array.length-1);

System.out.print("Values after the sort:\n");

for(i = 0; i <array.length; i++)

System.out.print(array[i]+" ");

System.out.println();

}

public static int partition(int arr[], int left, int right)

{

int i = left, j = right;

int tmp;

int pivot = arr[(left + right) / 2];

while (i <= j) {

while (arr[i] < pivot)

i++;

while (arr[j] > pivot)

j--;

if (i <= j) {

tmp = arr[i];

arr[i] = arr[j];

arr[j] = tmp;

i++;

j--;

}

};

return i;

}

public static void quickSort(int arr[], int left, int right) {

int index = partition(arr, left, right);

if (left < index - 1)

quickSort(arr, left, index - 1);

if (index < right)

quickSort(arr, index, right);

}

}

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

Replace the pivot variable assignment with:

```
int pivot = arr[left + rnd.nextInt(right - left)];
```

where rnd is a class Random object, which you could set as a private static final field.

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**