Three way partitioning of an array around a given range | Partitions arr [ 0. . n - 1 ] around [ lowVal . . highVal ] ; Initialize ext available positions for smaller ( than range ) and greater lements ; Traverse elements from left ; If current element is smaller than range , put it on next available smaller position . ; If current element is greater than range , put it on next available greater position . ; Driver code
def threeWayPartition ( arr , n , lowVal , highVal ) : NEW_LINE INDENT start = 0 NEW_LINE end = n - 1 NEW_LINE i = 0 NEW_LINE while i <= end : NEW_LINE INDENT if arr [ i ] < lowVal : NEW_LINE INDENT temp = arr [ i ] NEW_LINE arr [ i ] = arr [ start ] NEW_LINE arr [ start ] = temp NEW_LINE i += 1 NEW_LINE start += 1 NEW_LINE DEDENT elif arr [ i ] > highVal : NEW_LINE INDENT temp = arr [ i ] NEW_LINE arr [ i ] = arr [ end ] NEW_LINE arr [ end ] = temp NEW_LINE end -= 1 NEW_LINE DEDENT else : NEW_LINE INDENT i += 1 NEW_LINE DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 14 , 5 , 20 , 4 , 2 , 54 , 20 , 87 , 98 , 3 , 1 , 32 ] NEW_LINE n = len ( arr ) NEW_LINE threeWayPartition ( arr , n , 10 , 20 ) NEW_LINE print ( " Modified ▁ array " ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT print ( arr [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT