QuickSort | Java implementation of QuickSort ; A utility function to swap two elements ; 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 ; pivot ; Index of smaller element and indicates the right position of pivot found so far ; If current element is smaller than the pivot ; Increment index of smaller element ; The main function that implements QuickSort arr [ ] -- > Array to be sorted , low -- > Starting index , high -- > Ending index ; pi is partitioning index , arr [ p ] is now at right place ; Separately sort elements before partition and after partition ; Function to print an array ; Driver Code
import java . io . * ; class GFG { static void swap ( int [ ] arr , int i , int j ) { int temp = arr [ i ] ; arr [ i ] = arr [ j ] ; arr [ j ] = temp ; } static int partition ( int [ ] arr , int low , int high ) { int pivot = arr [ high ] ; int i = ( low - 1 ) ; for ( int j = low ; j <= high - 1 ; j ++ ) { if ( arr [ j ] < pivot ) { i ++ ; swap ( arr , i , j ) ; } } swap ( arr , i + 1 , high ) ; return ( i + 1 ) ; } static void quickSort ( int [ ] arr , int low , int high ) { if ( low < high ) { int pi = partition ( arr , low , high ) ; quickSort ( arr , low , pi - 1 ) ; quickSort ( arr , pi + 1 , high ) ; } } static void printArray ( int [ ] arr , int size ) { for ( int i = 0 ; i < size ; i ++ ) System . out . print ( arr [ i ] + " ▁ " ) ; System . out . println ( ) ; } public static void main ( 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 ) ; } }