First of all, here the return value is the number of elements less than the pivot
Pivot is just to minimize searching
So, now we are assuming our array has $10$ elements, $N=10 , k=8$
STEP 1: After Partition()
- left_end = 4
- left_end+1 < k
- so, (a+left_end+1, n-left_end-1, k-left_end-1)
- (a+5, 5, 3)
STEP 2: After Partition()
- left_end= 1
- left_end+1 < k
- so, (a+2, 3, 1)
STEP 3: After Partition()
- left_end = 2
- left_end +1 > k
- so, (a, 2, 1)
STEP 4: After Partition()
- left_end = 1
- left_end +1 > k
- so, (a,1,1)
STEP 5:
- left_end = 0
- left_end+1 = =k
- a[left_end] = 8
So, in STEP 1 and STEP 2 'else' condition is satisfied, and STEP 3 and STEP 4 'if ' condition is satisfied.
Here, partition is called and it returns the left_end value
Answer will be (A).