/*
This is an implementation of the quick sort algorithm.
Let n be the size of the list to sort
Best: O(nlog2(n)) time | O(log2(n)) space
Average: O(nlog2(n)) time | O(log2(n)) space
Worst: O(n^2) time | O(log2(n)) space
*/importjava.util.Arrays;publicclassQuickSort{publicstaticvoidmain(String[] args){int[] arr ={1,10,5,3,6};quickSort(arr);// Below prints: [1, 3, 5, 6, 10]System.out.println(Arrays.toString(arr));}publicstaticvoidquickSort(int[] array){// Sort array recursivelyquickSortUtil(array,0, array.length -1);}privatestaticvoidquickSortUtil(int[] array,int startIdx,int endIdx){// Base case: at this point array is sortedif(startIdx >= endIdx){return;}// Let first value be pivot// Sort every other number wrt to pivotint pivotIdx = startIdx;int leftIdx = startIdx +1;int rightIdx = endIdx;// Make sure that element at leftIdx <= to one at pivotIdx// and element at rightIdx is >= to one at pivotIdxwhile(leftIdx <= rightIdx){if(array[leftIdx]> array[pivotIdx]&& array[rightIdx]< array[pivotIdx]){swap(leftIdx, rightIdx, array);}if(array[leftIdx]<= array[pivotIdx]){
leftIdx++;}if(array[rightIdx]>= array[pivotIdx]){
rightIdx--;}}swap(pivotIdx, rightIdx, array);// At the end of current iteration, element at// pivot is in its final sorted positionquickSortUtil(array, startIdx, rightIdx -1);quickSortUtil(array, rightIdx +1, endIdx);}privatestaticvoidswap(int i,int j,int[] array){int temp = array[i];
array[i]= array[j];
array[j]= temp;}}
importjava.util.Arrays;//so fun to run//try it (;//Illustrate array in size of 100 Million Integers //global arrays only!!publicclassQuick{staticint[] arr =newint[10000000];publicstaticvoidmain(String[] args){//only use with global array!for(int i=0; i<arr.length;i++){
arr[i]=(int)(Math.random()*1000);}quickSort(0, arr.length-1, arr[arr.length-1]);//(send 0 to lowi,//send the last index in the array to higi, //send to pivot the last value in the array)System.out.println(Arrays.toString(arr));}publicstaticvoidquickSort(int lowi,int higi,int pivot){if(higi<=lowi)return;if(higi - lowi <1)return;if(higi - lowi ==1){if(arr[lowi]>arr[higi])swap(lowi, higi);return;}int temp, next = arr[lowi];int higiS = higi, lowiS = lowi,pos = lowi;while(higi-lowi >=1){if(next<pivot){
temp = arr[higi];if(higi == higiS)
temp = arr[++pos];else
temp = arr[higi];
arr[higi--]= next;}else{if(lowi<=pos)
temp = arr[++pos];else
temp = arr[lowi];
arr[lowi++]= next;}
next = temp;}if(lowi<pos)
lowi = pos-1;
arr[lowi]= pivot;quickSort(lowi+1, higiS, arr[higiS]);if(lowi-1>=0)quickSort(lowiS, lowi-1, arr[lowi-1]);return;}publicstaticvoidswap(int fI,int sI){int temp = arr[fI];
arr[fI]= arr[sI];
arr[sI]= temp;}}
// Java implementation of QuickSortimportjava.io.*;classGFG{// A utility function to swap two elementsstaticvoidswap(int[] arr,int i,int j){int temp = arr[i];
arr[i]= arr[j];
arr[j]= temp;}/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */staticintpartition(int[] arr,int low,int high){// pivotint pivot = arr[high];// Index of smaller element and// indicates the right position// of pivot found so farint i =(low -1);for(int j = low; j <= high -1; j++){// If current element is smaller// than the pivotif(arr[j]< pivot){// Increment index of// smaller element
i++;swap(arr, i, j);}}swap(arr, i +1, high);return(i +1);}/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index
*/staticvoidquickSort(int[] arr,int low,int high){if(low < high){// pi is partitioning index, arr[p]// is now at right placeint pi =partition(arr, low, high);// Separately sort elements before// partition and after partitionquickSort(arr, low, pi -1);quickSort(arr, pi +1, high);}}// Function to print an arraystaticvoidprintArray(int[] arr,int size){for(int i =0; i < size; i++)System.out.print(arr[i]+" ");System.out.println();}// Driver Codepublicstaticvoidmain(String[] args){int[] arr ={10,7,8,9,1,5};int n = arr.length;quickSort(arr,0, n -1);System.out.println("Sorted array: ");printArray(arr, n);}}// This code is contributed by Ayush Choudhary
staticvoidswap(int[] arr,int i,int j){int temp = arr[i];
arr[i]= arr[j];
arr[j]= temp;}staticintpartition(int[] arr,int low,int high){int pivot = arr[high];// Index of smaller element and// indicates the right position// of pivot found so farint i =(low -1);for(int j = low; j <= high -1; j++){// If current element is smaller // than the pivotif(arr[j]< pivot){// Increment index of // smaller element
i++;swap(arr, i, j);}}swap(arr, i +1, high);return(i +1);}staticvoidquickSort(int[] arr,int low,int high){if(low < high){// pi is partitioning index, arr[p]// is now at right place int pi =partition(arr, low, high);// Separately sort elements before// partition and after partitionquickSort(arr, low, pi -1);quickSort(arr, pi +1, high);}}