Okay so, let's say we have an array that is finished with partitioning and the result is
{3, 5, 3, 9, 17, 14, 24, 21, 19}
What is the pivot of the first partition step?
Apparently there are more than one answers to this but I only found one which is 9? Is there anymore I missed? If someone finds the other answer can you please explain how you found it?
There are two pivots possible for this partition.
The first one is 9 at the fourth position, which is obvious to find out since the first three numbers are smaller than 9 and the remaining numbers are greater than 9.
Another one is 3 at the first position, which is already located at the beginning of the array before the partition when it is placed at the end of the array, we cannot find any number which is smaller than 3, therefore no swaps are performed.
Try to use the first 3 as the pivot and perform the partition, you will get the same result. Assuming the swapping pointer on the left looks for a number greater or equal to the pivot, and the swapping point on the right looks for a number smaller than the pivot.
Which means, for the array {3, 5, 3, 9, 17, 14, 24, 21, 19},
3 5 3 9 17 14 24 21 19
19 5 3 9 17 14 24 21 3 #Swap pivot to the end
[19] 5 3 9 17 14 24 21 3
#Left locks 19 >= 3, right cannot find any number < 3, end of swapping
3 5 3 9 17 14 24 21 19
#Swap pivot back to the position where left and right pointers meet
#End of algorithm