2
Doubt:
To order arrays with heapsort, it is customary to simulate in them trees with up to two children per parent, no longer. My question is whether there are studies, implementations, experiments, reports, accessible data that investigate heapsort performance in arrays simulating trees with larger numbers of children per parent.
Details:
I implemented array sorting with heapsort using the maximum of two children per parent. With the notions of code complexity I have, it seemed to me that the number of comparisons of a heapsort interaction (definition of the last element of the current subarray) is, in the worst case, around 2*log2(n), as there are two comparisons per depth level and the depth is around log2(n). But what if I "adopted more children"?
Thinking about it, I suppose we can adapt the code for more than two children by adding, for each additional child, a comparison by depth level. It increases the comparisons by depth, but the depth decreases, thus perhaps making fewer comparisons. The formula I found to estimate comparisons by interaction depending on the number F of children is F*logF(n).
If I’m right, mathematically the ideal would be F = e ~ 2.71828, but you can’t. Increasing from two children to three children would decrease the number of comparisons (-5,36% in F=3). Increase from two to four children, would conserve (0,00% in F=4). Increasing from two to five children or more would increase comparisons (+7,67% if F=5). So, mathematically it is like this, but how is the performance in practice? Has it already been tested? There are known data?
Roughly speaking, the adoption of an extra child would cause asymptotic complexity to be multiplied by a constant term, so it would be within the same time complexity class. Real lead time, though, I don’t know.
– Jefferson Quesado
Exactly. Asymptotically, nothing changes. I want to know how it is in practice. I may have to try it myself. I can’t find anything on the internet.
– RHER WOLF
I created a repository in Java to test sorting algorithms, want to include there?
– Jefferson Quesado
Okay, I look. Thank you.
– RHER WOLF
https://gitlab.com/totalcross/stack-overflow/tree/master/performance-sort If you can make the ternary heap, it will be a great contribution
– Jefferson Quesado
Right. I actually implemented it in C++, but I can convert it to java if I can implement it right.
– RHER WOLF
O(log3(n))andO(log2(n))are asymptotically equivalent. Which in a way I’m saying what @Jeffersonquesado said but otherwise.– Isac
Sei... log3(n)=0,63093log2(n)... therefore for n>1 has 0,63092log2(n)<log3(n)<0,63094*log2(n)... logo log3(n)=THETA(log2(n)), etc etc etc. And the practical result of the change in implementation, outside the field of asymptotic analysis?
– RHER WOLF
Making the two part of the same temporal class then will only make a difference to a very low N. Which means the gain is not significant for so few operations
– Isac
Even an algorithm 10%, 5%, 3%, even 1% faster is more efficient. Refining it can add more percentages and come up with something really cool. I want to know more about this.
– RHER WOLF
@RHERWOLF , something new? Managed to do and get the performance results?
– Jefferson Quesado
I was able to implement it, it has not been wrong... but I could not make the measurements. The differences in results do not cover the measurement errors. I need more precision. I would also like a way to develop arrays in the worst case of heapsort and other algorithms to compare them, even asymptotically insignificant.
– RHER WOLF