Three way partitioning of an array around a given range | C ++ program to implement three way partitioning 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
#include <iostream> NEW_LINE using namespace std ; void threeWayPartition ( int arr [ ] , int n , int lowVal , int highVal ) { int start = 0 , end = n - 1 ; for ( int i = 0 ; i <= end ; ) { if ( arr [ i ] < lowVal ) swap ( arr [ i ++ ] , arr [ start ++ ] ) ; else if ( arr [ i ] > highVal ) swap ( arr [ i ] , arr [ end -- ] ) ; else i ++ ; } } int main ( ) { int arr [ ] = { 1 , 14 , 5 , 20 , 4 , 2 , 54 , 20 , 87 , 98 , 3 , 1 , 32 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; threeWayPartition ( arr , n , 10 , 20 ) ; cout << " Modified ▁ array ▁ STRNEWLINE " ; for ( int i = 0 ; i < n ; i ++ ) cout << arr [ i ] << " ▁ " ; }