QuickSort
//We chose pivot
//All elements samller than pivot on the left
//All elements greater than pivot on the right
//Pivot doesn't have to end at its right full position after partition
//pueden pasarse el pivot hasta que ambos punteros se encuentren
//RUN TIME: O(Nlog(N)) -- on average (depends on pivot we chose)
//SPACE COMPLEXITY : null
public class Solution{
public static void quickSort(int[] array){
quickSort(array, 0, array.length-1);
}
public static void quickSort(int[]array, int left, int right){
if(left >= right){
return;
}
int pivot = array[(left + right)/2];
int index = partition(array, left, right, pivot);
quickSort(array, left, index-1);
quickSort(array, index, right);
}
public static int partition(int[] array, int left, int right, int pivot){
while(left < right){
while(array[left]<pivot){
left ++;
}
while (array[right] > pivot){
right--;
}
if(left <= right){
swap(array, left, right);
left++;
right--;
}
}
return left;
}
}