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
function partition ( & $ arr , $ l , $ h ) { $ x = $ arr [ $ h ] ; $ i = ( $ l - 1 ) ; for ( $ j = $ l ; $ j <= $ h - 1 ; $ j ++ ) { if ( $ arr [ $ j ] <= $ x ) { $ i ++ ; swap ( $ arr [ $ i ] , $ arr [ $ j ] ) ; } } swap ( $ arr [ $ i + 1 ] , $ arr [ $ h ] ) ; return ( $ i + 1 ) ; }