Posts: 2020
Threads: 133
Joined: July 26, 2017
Reputation:
5
C++ "sort"
November 13, 2019 at 12:14 pm
Does somebody have an explanation, why does C++ "sort" behave like this?
![[Image: Comparisons_on_different_permutations_Cxx.png]](https://github.com/FlatAssembler/ArithmeticExpressionCompiler/raw/master/QuickSort/TestResults/Comparisons_on_different_permutations_Cxx.png)
I was considering writing a referat about my attempt to implement efficient sorting function in my prpgramming language (called AEC), and I think it would be interesting to add an explanation for this into my paper.
Posts: 2020
Threads: 133
Joined: July 26, 2017
Reputation:
5
RE: C++ "sort"
December 12, 2019 at 4:51 am
Anyway, done some new experiment, the results of which you can see here:
![[Image: number_of_sorted_elements_logarithm.png]](https://github.com/FlatAssembler/ArithmeticExpressionCompiler/raw/master/QuickSort/TestResults/number_of_sorted_elements_logarithm.png)
C++ represents the C++ "sort" function, while "C" represents my naive implementation of QuickSort in C.
Posts: 2872
Threads: 8
Joined: October 4, 2017
Reputation:
22
RE: C++ "sort"
December 12, 2019 at 9:48 am
(This post was last modified: December 12, 2019 at 9:49 am by Abaddon_ire.)
This is the Atheist Forum, not the "Do-my-homework-for-me" Forum.
Posts: 2020
Threads: 133
Joined: July 26, 2017
Reputation:
5
RE: C++ "sort"
December 12, 2019 at 11:21 am
(December 12, 2019 at 9:48 am)Abaddon_ire Wrote: This is the Atheist Forum, not the "Do-my-homework-for-me" Forum.
Atheism is not the only thing atheists talk about. Besides, I don't really think this is a request to do my homework for me, I've already done quite a bit of research and presented it here. More like "help me with my homework". And this isn't really a homework assignment, it's much more complicated than something you'd get as one.
Posts: 2020
Threads: 133
Joined: July 26, 2017
Reputation:
5
RE: C++ "sort"
December 12, 2019 at 2:42 pm
Here is probably an even better measurement:
![[Image: number_of_sorted_elements_logarithm_double_shuffled.png]](https://github.com/FlatAssembler/ArithmeticExpressionCompiler/raw/master/QuickSort/TestResults/number_of_sorted_elements_logarithm_double_shuffled.png)
Posts: 2020
Threads: 133
Joined: July 26, 2017
Reputation:
5
RE: C++ "sort"
December 13, 2019 at 2:50 pm
(This post was last modified: December 13, 2019 at 3:10 pm by FlatAssembler.
Edit Reason: typo
)
So, what do you think about this:
https://github.com/FlatAssembler/Arithme.../README.MD Wrote:The most important conclusion of my measurements is that the number of comparisons done by a naive implementation of QuickSort can be predicted by the formula:
f(n,s)=exp((ln(n)+ln(ln(n)))*1.05+(ln(n)-ln(ln(n)))*0.83*abs(2.38854*pow(s,7)-0.284258*pow(s,6)-1.87104*pow(s,5)+0.372637*pow(s,4)+0.167242*pow(s,3)-0.0884977*pow(s,2)+0.315119*s))
In that formula, 'n' is the number of elements in an array, and 's' is the pre-sortedness of an array. If an element is sorted before QuickSort is called, 's' is 1. If it's reverse-sorted, 's' is -1. If 's' is randomly shuffled, 's' is approximately 0.
Posts: 17238
Threads: 462
Joined: March 29, 2015
Reputation:
30
RE: C++ "sort"
December 13, 2019 at 4:45 pm
But why use C++? Isn't C# better?
teachings of the Bible are so muddled and self-contradictory that it was possible for Christians to happily burn heretics alive for five long centuries. It was even possible for the most venerated patriarchs of the Church, like St. Augustine and St. Thomas Aquinas, to conclude that heretics should be tortured (Augustine) or killed outright (Aquinas). Martin Luther and John Calvin advocated the wholesale murder of heretics, apostates, Jews, and witches. - Sam Harris, "Letter To A Christian Nation"
Posts: 2020
Threads: 133
Joined: July 26, 2017
Reputation:
5
RE: C++ "sort"
December 14, 2019 at 5:06 am
(December 13, 2019 at 4:45 pm)Fake Messiah Wrote: But why use C++? Isn't C# better? Well, I don't know any C# right now. And I doubt it's so much better for this task to be worth learning.
Posts: 2872
Threads: 8
Joined: October 4, 2017
Reputation:
22
RE: C++ "sort"
December 14, 2019 at 10:29 pm
(December 14, 2019 at 5:06 am)FlatAssembler Wrote: (December 13, 2019 at 4:45 pm)Fake Messiah Wrote: But why use C++? Isn't C# better? Well, I don't know any C# right now. And I doubt it's so much better for this task to be worth learning.
Who cares. The various flavours of sorts are a noob exercise. Grow up.
Posts: 2020
Threads: 133
Joined: July 26, 2017
Reputation:
5
RE: C++ "sort"
December 15, 2019 at 3:55 am
(December 14, 2019 at 10:29 pm)Abaddon_ire Wrote: (December 14, 2019 at 5:06 am)FlatAssembler Wrote: Well, I don't know any C# right now. And I doubt it's so much better for this task to be worth learning.
Who cares. The various flavours of sorts are a noob exercise. Grow up. And how do you think people invented IntroSort? By systematically studying various flavours of sort, much more so than you and I have. That isn't just a noob exercise.
|
