首页 > 代码库 > 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]; } }}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。