I have no idea why we got different things for mergesort, but it's probably where we count the comparisons and swaps... guess this is not really a scientific way.
Type: Posts; User: cyberfish
I have no idea why we got different things for mergesort, but it's probably where we count the comparisons and swaps... guess this is not really a scientific way.
That's interesting... for my implementation, it's "0 1 2 3 4 5 6 7 8 9" for mergesort. Further investigation reveals that all permutations take exactly the same number of comparisons, suggesting that...
I would add another variable
int max_comps = -1;
And print out "myarray" whenever mergecomps > max_comps, and update max_comps.
(Or just remember the "myarray" associated with the max_comps.
Yes, I brute-forced it.
The code is quite messy, though.
Hint: use std::next_permutation() in <algorithm>
I recommend the global counter approach. Increment it by one everytime you compare/swap in the sort.
I just did it with my 6 sorting functions I wrote some time ago for practice. The results are...
Even at 10MHz it will probably sort 8 elements before you notice it. You'll need to underclock it to 10Hz or something. And make sure you get a lightweight OS, or you will be sitting there for a few...
If you use brute-force (try all permutations) to find the worst case for (say) 8 elements, do you notice a pattern?
That's how I would do it. No idea if it will work, though.