Given the algorithm here, look at the scenario where i is at "X", the following happens:
Scenario: i -> "X", "X" > "P"
1. swap("X", "Z"), gt--; // the value at i is now "Z", which is still > "P"
2. swap("Z", "Y"), gt--; // the value at i is now "Y", which is still > "P"
3. swap("Y", "C"), gt--; // Now we finally get a value at i "C" which is < "P"
// Now we can swap values at i and lt, and increrement them
4. swap("P", "C"), i++, lt++;
Why don't we just decrement gt until gt points to a value that is < the value at lt ("P" in this case), then we swap this value with the value at i. This will save swapping operations.
So if we do that for the scenario mentioned above, we'll do:
1. gt--
2. gt--
3. swap("X", "C"), gt--;
// Now we can swap values at i and lt, and increrement them
4. swap("P", "C"), i++, lt++;
Is this excessive swapping needed for the algorithm? does it improve performance in some way?
If it does improve performance, how?
If it doesn't affect performance, please give a proper explanation or a proof as to why this it does not affect performance.
Also, would the second method I mentioned affect performance in any way? please explain why.
P.S. "Affect performance" as used above means either improve/degrade performance.