Dual pivot Quicksort | Python3 program to implement dual pivot QuickSort ; lp means left pivot and rp 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 ; Driver code
def dualPivotQuickSort ( arr , low , high ) : NEW_LINE INDENT if low < high : NEW_LINE INDENT lp , rp = partition ( arr , low , high ) NEW_LINE dualPivotQuickSort ( arr , low , lp - 1 ) NEW_LINE dualPivotQuickSort ( arr , lp + 1 , rp - 1 ) NEW_LINE dualPivotQuickSort ( arr , rp + 1 , high ) NEW_LINE DEDENT DEDENT def partition ( arr , low , high ) : NEW_LINE INDENT if arr [ low ] > arr [ high ] : NEW_LINE INDENT arr [ low ] , arr [ high ] = arr [ high ] , arr [ low ] NEW_LINE DEDENT j = k = low + 1 NEW_LINE g , p , q = high - 1 , arr [ low ] , arr [ high ] NEW_LINE while k <= g : NEW_LINE INDENT if arr [ k ] < p : NEW_LINE INDENT arr [ k ] , arr [ j ] = arr [ j ] , arr [ k ] NEW_LINE j += 1 NEW_LINE DEDENT elif arr [ k ] >= q : NEW_LINE INDENT while arr [ g ] > q and k < g : NEW_LINE INDENT g -= 1 NEW_LINE DEDENT arr [ k ] , arr [ g ] = arr [ g ] , arr [ k ] NEW_LINE g -= 1 NEW_LINE if arr [ k ] < p : NEW_LINE INDENT arr [ k ] , arr [ j ] = arr [ j ] , arr [ k ] NEW_LINE j += 1 NEW_LINE DEDENT DEDENT k += 1 NEW_LINE DEDENT j -= 1 NEW_LINE g += 1 NEW_LINE arr [ low ] , arr [ j ] = arr [ j ] , arr [ low ] NEW_LINE arr [ high ] , arr [ g ] = arr [ g ] , arr [ high ] NEW_LINE return j , g NEW_LINE DEDENT arr = [ 24 , 8 , 42 , 75 , 29 , 77 , 38 , 57 ] NEW_LINE dualPivotQuickSort ( arr , 0 , 7 ) NEW_LINE print ( ' Sorted ▁ array : ▁ ' , end = ' ' ) NEW_LINE for i in arr : NEW_LINE INDENT print ( i , end = ' ▁ ' ) NEW_LINE DEDENT print ( ) NEW_LINE