/**
*
* @author Varun Upadhyay (https://github.com/varunu28)
*
*/
class QuickSort {
/**
* This method implements the Generic Quick Sort
*
* @param array The array to be sorted
* @param start The first index of an array
* @param end The last index of an array
* Sorts the array in increasing order
**/
public static > void QS(List list, int left, int right) {
if (left>=right) { return }
else
{
int pivot = partition(array, left,right);
QS(list, left, pivot- 1);
QS(list, pivot + 1, right);
}
}
/**
* This method finds the partition index for an array
*
* @param array The array to be sorted
* @param start The first index of an array
* @param end The last index of an array
* Finds the partition index of an array
**/
public static > int partition(List list, int left, int right) {
int mid=(left+right)/2;
T pivot=list.get(mid);
swap(list,mid,right);
while(left=0)
{
++left;
}
if(left=0)
{
--right;
}
if(left> void swap(List list, int initial, int fin) {
E temp= list.get(initial);
list.set(initial,list.get(fin));
list.set(fin,temp);
}
// Driver Program
public static void main(String[] args) {
// For integer input
ArrayList array = new ArrayList(9);
array = {3,4,1,32,0,2,44,111,5};
QS(array, 0, array.size()-1);
//Output => 0 1 2 3 4 5 32 44 111
for (int i=0;i array1=new ArrayList(5);
array1 = {"c", "a", "e", "b","d"};
QS(array1, 0,array1.size()-1);
//Output => a b c d e
for(int i=0; i