It has been discussed in many places many times I believe, but I have been searching for 3 days now and did not realize how this is happening. My question is:
Where is the second pointer, if we take the first or the last element as a pivot?
What I literally mean:
Case 1
Central array element as a pivot
This is all clear as 5 is in the center, we go ahead and find the elements that comply the conditions:
1.) element < pivot for the left side if found we stop the pointer
2.) element > pivot for the right side if found we stop the pointer
3.) swap the elements where we stopped the pointers during steps 1 and 2
Case 2: (unclear one)
first or last element as a pivot
Here is unclear where should I put both pointers to start the finding of an elements, and which direction regarding pivot should I move? Should this be two pointers as well, and how should they be moved? Still should be exectly two pointers?
If two pointers are being used, it's some variation of Hoare partition scheme, where the pointers start off at the first and last element of the array, and advance towards each other while scanning for "out of place" elements. If the first or last element is chosen as the pivot, the first swap will involve the pivot.
Note that Hoare algorithm normally includes the pivot in one of the partitions. This creates an issue if using the first or last element as a pivot, as data patterns like already sorted data would result in stack overflow as the split will always be 0 elements and n elements. To resolve this issue, the algorithm would need to exclude the pivot in the recursive calls.
