kobe kobe - 3 months ago 7
Java Question

Doing quick sort using random pivot element instead of mid element code

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

}

Per Per
Answer

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.