14

Algorithm

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.

2 Answers 2

8
+250

You are right, the extra swap operations are not necessary, this algorithm here is best for clarity, but not for performance. See the discussion of Quick Sort (3 Way Partition).

In Quicksort is optimal by Robert Sedgewich himself, he has a different approach that uses much less swap operation, but you can imagine it also needs more code, and is less clear than the algorithm in the demo.

enter image description here

7

The algorithm is based on Dijkstra's solution to “The Problem of the Dutch National Flag” which appeared (p.111) in his book “A Discipline of Programming” published in 1976. Dijkstra’s goal with the book was to derive provable correct solutions to multiple problems. Not just presenting the final result, but actually going through the design process.

In “The Problem of the Dutch National Flag” Dijkstra envisions a row of buckets (think array) each containing a single pebble having either the color red, white or blue (the colors of the Dutch flag). There is a mini-computer with just two operations. It can swap the contents of two buckets and it can inspect the color of the pebble in a bucket. He restricts the use of the latter operation to a single inspection of each bucket. The latter is sufficient, hence that is what he chooses in his usual elegant minimalistic style. In terms of proving the correctness having as few cases as possible to consider is definitely an advantage. Here is a quote from one of his writings: “… become extremely suspicious as soon as one finds oneself faced with a case analysis which has to distinguish between a great number of cases”.

Transformed to the sorting problem, the equivalent would be to have at most N comparisons. This is actually quite common. In the C++ standard the complexity of the different sorting algorithms and the heap operations are in terms of number of comparisons. Not the number of swaps. The thinking is that swapping is cheap, if not use indirection (pointers) to make it cheap. Comparisons however can be expensive. So, it makes more sense to state the complexity in terms of number of comparisons.

Yes, you could reduce the number of swaps, but not if you want to have at most N comparisons.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.