/**
* Created on 11-Aug-19 10:02 AM.
*
* @author Aayush
*/
public class RandomizedQuickSort {
public static void sort(int[] array) {
sort(array, 0, array.length-1);
}
public static void sort(int[] array, int startIndex, int endIndex){
if(startIndex >= endIndex) return;
int partitionIndex = partition(array, startIndex, endIndex);
sort(array, startIndex, partitionIndex-1);
sort(array, partitionIndex+1, endIndex);
}
/**
* Returns the partition index, where the pivot element resides.
* On the left of the pivot element, all the lower values reside.
* On the right of the pivot element, all the higher values reside.
*
* @param array
* @param startIndex
* @param endIndex
* @return
*/
private static int partition(int[] array, int startIndex, int endIndex) {
int randomIndex = getRandomNumber(startIndex, endIndex);
int pivot = array[randomIndex]; // getting the random pivot
array[endIndex] = swap(pivot, array[randomIndex] = array[endIndex]); //putting the random pivot at the end index
int partitionIndex = startIndex;
for (int i=startIndex; i<endIndex; i++) {
if(array[i] <= pivot){
array[i] = swap(array[partitionIndex], array[partitionIndex] = array[i]);
partitionIndex++;
}
}
array[partitionIndex] = swap(array[endIndex], array[endIndex] = array[partitionIndex]);
return partitionIndex;
}
/**
* A chucklesome swap function.
*
* E.g. to swap 'a' & 'b',
* store the returned value of this method to 'a',
* and call the method with values :
* #swapValue = 'b' and #swapYourselfWhileCalling = 'b=a'
*
* @param swapValue Value that will be returned
* @param swapYourselfWhileCalling swap the other way while calling
* @return #swapValue
*/
private static int swap(int swapValue, int swapYourselfWhileCalling){ return swapValue;}
/**
* Calculates a random value i.e.
* greater than or equal to start and
* less than end
*
* @param start
* @param end
* @return Returns a random number based on the above explanation
*/
private static int getRandomNumber(int start, int end){
int randomIndex;
do{
randomIndex = (int) (Math.random() * end);
}while(randomIndex < start);
return randomIndex;
}
}
Currently the above handles integer sorting in ascending order. (I’ve chosen a basic one, so it would be easier to understand)
It can be upgraded to sort other types, and also the sorting order can be variable.
Any related questions, drop your question below.
Also, everyone loves appreciations 🙂
That’s All. P)
Happy Java-ing.
-Aayush Shrivastava
Programs 