Dual pivot Quicksort | Java program to implement dual pivot QuickSort ; piv [ ] stores left pivot and right pivot . piv [ 0 ] means left pivot and piv [ 1 ] means right pivot ; p is the left pivot , and q is the right pivot . ; If elements are less than the left pivot ; If elements are greater than or equal to the right pivot ; Bring pivots to their appropriate positions . ; Returning the indices of the pivots because we cannot return two elements from a function , we do that using an array . ; Driver code
class GFG { static void swap ( int [ ] arr , int i , int j ) { int temp = arr [ i ] ; arr [ i ] = arr [ j ] ; arr [ j ] = temp ; } static void dualPivotQuickSort ( int [ ] arr , int low , int high ) { if ( low < high ) { int [ ] piv ; piv = partition ( arr , low , high ) ; dualPivotQuickSort ( arr , low , piv [ 0 ] - 1 ) ; dualPivotQuickSort ( arr , piv [ 0 ] + 1 , piv [ 1 ] - 1 ) ; dualPivotQuickSort ( arr , piv [ 1 ] + 1 , high ) ; } } static int [ ] partition ( int [ ] arr , int low , int high ) { if ( arr [ low ] > arr [ high ] ) swap ( arr , low , high ) ; int j = low + 1 ; int g = high - 1 , k = low + 1 , p = arr [ low ] , q = arr [ high ] ; while ( k <= g ) { if ( arr [ k ] < p ) { swap ( arr , k , j ) ; j ++ ; } else if ( arr [ k ] >= q ) { while ( arr [ g ] > q && k < g ) g -- ; swap ( arr , k , g ) ; g -- ; if ( arr [ k ] < p ) { swap ( arr , k , j ) ; j ++ ; } } k ++ ; } j -- ; g ++ ; swap ( arr , low , j ) ; swap ( arr , high , g ) ; return new int [ ] { j , g } ; } public static void main ( String [ ] args ) { int [ ] arr = { 24 , 8 , 42 , 75 , 29 , 77 , 38 , 57 } ; dualPivotQuickSort ( arr , 0 , 7 ) ; System . out . print ( " Sorted ▁ array : ▁ " ) ; for ( int i = 0 ; i < 8 ; i ++ ) System . out . print ( arr [ i ] + " ▁ " ) ; System . out . println ( ) ; } }