首页 > 代码库 > Partition an array around an interger

Partition an array around an interger

Partition an array of integers around a value such taht all elements less than x come before elements greater than or equal to x.

Idea: Just use of subroutine PARTION of quicksort() with a slight modification.

array[start, end] to be partitioned around value x.

We need to additional pointers i and j, to maintain an invariant, which is true at all times:

  array[start, i] stores elements less than x

  array[i+1, j-1] stores elements greater than or equal to x

  array[j, end] stores elements which haven‘t been explored yet.

   

void Partition(A, start, end){    int i = start - 1;    for(int j = start; j <= end; ++j){        if(A[j] < x){            i++;            swap A[i] with A[j];        }    }}