ˋˋˋ
function partition(nums, left, right) {
const pivot = const pivotPos = nums[right]
// left bucket is the contiguous part where numbers are smaller than pivot
// right bucket is the contiguous part where numbers are greater than pivot
let leftBucketExclusiveEnd = left
for (let curPos = leftBucketExclusiveEnd; curPos < right - 1; curPos++) {
if (nums[curPos] < pivot) {
swap(nums, curPos, leftBucketExclusiveEnd)
leftBucketExclusiveEnd++;
}
}
// place the pivot between two segments
swap (nums, leftBucketExclusiveEnd, pivotPos)
return pivotPos
}
ˋˋˋ
The left bucket range is nums[0 ... leftBucketExclusiveEnd - 1], we start with an empty bucket, and we try to check the exclusive end number. If that number is smaller than pivot, we push this number into bucket ( by moving the swapping the leftBucketExclusiveEnd value with that number, and move leftBucketExclusiveEnd point to next element)
This trick make use of the charateristic that this is a contiguous list. So that we can define two ranges by ony one pointer (leftBucketExclusiveEnd)
