On 02/06/2016 02:00 PM, Andrei Alexandrescu wrote:
On 02/05/2016 08:58 PM, Timon Gehr wrote:
On 02/06/2016 02:39 AM, Andrei Alexandrescu wrote:
On 02/04/2016 03:30 PM, Timon Gehr wrote:
At most 6 comparisons, <=3 swaps, idempotent (optimal number of swaps):
What is the minimum number of comparisons? Thx! -- Andrei
There is no partition algorithm that uses <= 5 comparisons in all cases.
(If that is what you're asking.)
Was asking about this particular one. For example, the maximum
comparisons is 6, but it would be good to know the average number of
comparisons. I know I could read through the code, but it's hairy.
Thanks! -- Andrei
All versions posted in this thread do 6 comparisons on all code paths.
(It is not possible to do better.)
BTW, the code I had posted earlier suffers from the following flaws:
- Branches were cut off too early, so -version=SHORT didn't actually
find the shortest code. [1]
- The code (by necessity) only performs the optimal number of swaps if
all input elements are different. While it leaves already partitioned
integer arrays in the same state as they were encountered, if multiple
input elements are equal, the generated algorithm will sometimes swap
them, violating idempotence if input elements can compare equal but be
different. However, tn's versions fix this: they never perform any swaps
if the input array is already partitioned.
[1] This seems to be the shortest code that satisfies the specification
I have given (<=6 comparisons, optimal number of swaps) for permutations
and that performs all the comparing before all the swapping:
void partition5(ref int[5] a){
if(a[0]<a[2]){if(a[1]<a[3]){if(a[0]<a[1]){if(a[2]<a[4]){if(a[1]<a[2]){if(a[3]<a[2]){swap(a[3],a[2]);}}else{if(a[1]<a[4]){swap(a[1],a[2]);}else{swap(a[4],a[2]);swap(a[1],a[4]);}}}else{if(a[1]<a[4]){if(a[3]<a[4]){swap(a[3],a[2]);}else{swap(a[4],a[2]);}}else{if(a[1]<a[2]){swap(a[1],a[2]);swap(a[1],a[4]);}else{swap(a[1],a[4]);}}}}else{if(a[3]<a[4]){if(a[0]<a[3]){if(a[3]<a[2]){swap(a[3],a[2]);}}else{if(a[0]<a[4]){swap(a[0],a[2]);swap(a[0],a[3]);}else{swap(a[4],a[2]);swap(a[0],a[3]);}}}else{if(a[0]<a[4]){if(a[4]<a[2]){swap(a[4],a[2]);}}else{if(a[0]<a[3]){swap(a[0],a[2]);swap(a[0],a[4]);}else{swap(a[3],a[2]);swap(a[0],a[4]);}}}}}else{if(a[0]<a[3]){if(a[2]<a[4]){if(a[2]<a[3]){if(a[3]<a[4]){swap(a[3],a[2]);swap(a[1],a[3]);}else{swap(a[4],a[2]);swap(a[1],a[4]);}}else{if(a[1]<a[2]){swap(a[1],a[2]);swap(a[1],a[3]);}else{swap(a[1],a[3]);}}}else{if(a[3]<a[4]){if(a[1]<a[4]){swap(a[1],a[2]);swap(a[1],a[3]);}else{swap(a[4],a[2]);swap(a[1],a[3]);}}else{if(a[2]<a[3]){swap(a[1],a[4]);}else{swap!
(a[3],a[2]
);swap(a[1],a[4]);}}}}else{if(a[1]<a[4]){if(a[0]<a[1]){if(a[1]<a[2]){swap(a[1],a[2]);swap(a[1],a[3]);}else{swap(a[1],a[3]);}}else{if(a[0]<a[4]){swap(a[0],a[2]);swap(a[0],a[3]);}else{swap(a[4],a[2]);swap(a[0],a[3]);}}}else{if(a[0]<a[4]){if(a[2]<a[4]){swap(a[1],a[3]);}else{swap(a[4],a[2]);swap(a[1],a[3]);}}else{if(a[0]<a[1]){swap(a[0],a[2]);swap(a[0],a[3]);swap(a[1],a[4]);}else{swap(a[1],a[2]);swap(a[0],a[3]);swap(a[1],a[4]);}}}}}}else{if(a[3]<a[4]){if(a[0]<a[4]){if(a[1]<a[3]){if(a[0]<a[3]){if(a[0]<a[1]){swap(a[1],a[2]);}else{swap(a[0],a[2]);}}else{if(a[2]<a[3]){swap(a[3],a[2]);swap(a[0],a[3]);}else{swap(a[0],a[3]);}}}else{if(a[0]<a[1]){if(a[0]<a[3]){swap(a[3],a[2]);swap(a[1],a[3]);}else{swap(a[0],a[2]);swap(a[1],a[3]);}}else{if(a[1]<a[2]){swap(a[0],a[3]);}else{swap(a[1],a[2]);swap(a[0],a[3]);}}}}else{if(a[1]<a[2]){if(a[2]<a[4]){if(a[2]<a[3]){swap(a[3],a[2]);swap(a[0],a[3]);}else{swap(a[0],a[3]);}}else{if(a[1]<a[4]){swap(a[4],a[2]);swap(a[0],a[3]);}else{swap(a[1],a[2]);swap(a[!
0],a[3]);s
wap(a[1],a[4]);}}}else{if(a[1]<a[4]){if(a[1]<a[3]){swap(a[3],a[2]);swap(a[0],a[3]);}else{swap(a[1],a[2]);swap(a[0],a[3]);}}else{if(a[2]<a[4]){swap(a[4],a[2]);swap(a[0],a[3]);swap(a[1],a[4]);}else{swap(a[0],a[3]);swap(a[1],a[4]);}}}}}else{if(a[0]<a[3]){if(a[1]<a[4]){if(a[0]<a[4]){if(a[0]<a[1]){swap(a[1],a[2]);}else{swap(a[0],a[2]);}}else{if(a[2]<a[4]){swap(a[4],a[2]);swap(a[0],a[4]);}else{swap(a[0],a[4]);}}}else{if(a[0]<a[1]){if(a[0]<a[4]){swap(a[4],a[2]);swap(a[1],a[4]);}else{swap(a[0],a[2]);swap(a[1],a[4]);}}else{if(a[1]<a[2]){swap(a[0],a[4]);}else{swap(a[1],a[2]);swap(a[0],a[4]);}}}}else{if(a[1]<a[2]){if(a[2]<a[3]){if(a[2]<a[4]){swap(a[4],a[2]);swap(a[0],a[4]);}else{swap(a[0],a[4]);}}else{if(a[1]<a[3]){swap(a[3],a[2]);swap(a[0],a[4]);}else{swap(a[1],a[2]);swap(a[0],a[3]);swap(a[1],a[4]);}}}else{if(a[1]<a[3]){if(a[1]<a[4]){swap(a[4],a[2]);swap(a[0],a[4]);}else{swap(a[1],a[2]);swap(a[0],a[4]);}}else{if(a[2]<a[3]){swap(a[3],a[2]);swap(a[0],a[3]);swap(a[1],a[4]);}else{swap(a[0!
],a[3]);sw
ap(a[1],a[4]);}}}}}}
}
