Our server costs ~$56 per month to run. Please consider donating or becoming a Patron to help keep the site running. Help us gain new members by following us on Twitter and liking our page on Facebook!
Current time: August 4, 2021, 7:45 am

Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
C++ "sort"
#11
RE: C++ "sort"
(December 15, 2019 at 3:55 am)FlatAssembler Wrote:
(December 14, 2019 at 10:29 pm)Abaddon_ire Wrote: 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.

Why did you not develop your own sort algorithm? Why did you find it necessary to steal someone elses? Musser invented introsort as a hybrid of other sort algo's. Good for him. Can't say I like it much.
Reply
#12
RE: C++ "sort"
Abaddon_ire Wrote:Why did you not develop your own sort algorithm? Why did you find it necessary to steal someone elses? Musser invented introsort as a hybrid of other sort algo's. Good for him. Can't say I like it much.
I wouldn't say it's stealing to continue someone's work. People who discovered an efficient algorithm don't own those algorithms, they existed before they were discovered in the same sense that the Pythagorean theorem existed before it was discovered: it exists in our world (and any world which approximately obeys the Euclidean Fifth Postulate) independently of whether it's discovered or not. And efficient sorting algorithms exist in all worlds in which a RAM machine is possible.
What do you mean you don't like Introsort? It's demonstrably the most efficient known algorithm for sorting large arrays that doesn't make assumptions about whether they are already partially or completely sorted.
Reply
#13
RE: C++ "sort"
(December 15, 2019 at 1:41 pm)FlatAssembler Wrote:
Abaddon_ire Wrote:Why did you not develop your own sort algorithm? Why did you find it necessary to steal someone elses? Musser invented introsort as a hybrid of other sort algo's. Good for him. Can't say I like it much.
I wouldn't say it's stealing to continue someone's work. People who discovered an efficient algorithm don't own those algorithms, they existed before they were discovered in the same sense that the Pythagorean theorem existed before it was discovered: it exists in our world (and any world which approximately obeys the Euclidean Fifth Postulate) independently of whether it's discovered or not. And efficient sorting algorithms exist in all worlds in which a RAM machine is possible.
What do you mean you don't like Introsort? It's demonstrably the most efficient known algorithm for sorting large arrays that doesn't make assumptions about whether they are already partially or completely sorted.

Try writing SQL at the command line. Then get back to me.

I have no interest in doing your first year homework vicariously.
Reply
#14
RE: C++ "sort"
(December 15, 2019 at 3:33 pm)Abaddon_ire Wrote:
(December 15, 2019 at 1:41 pm)FlatAssembler Wrote: I wouldn't say it's stealing to continue someone's work. People who discovered an efficient algorithm don't own those algorithms, they existed before they were discovered in the same sense that the Pythagorean theorem existed before it was discovered: it exists in our world (and any world which approximately obeys the Euclidean Fifth Postulate) independently of whether it's discovered or not. And efficient sorting algorithms exist in all worlds in which a RAM machine is possible.
What do you mean you don't like Introsort? It's demonstrably the most efficient known algorithm for sorting large arrays that doesn't make assumptions about whether they are already partially or completely sorted.

Try writing SQL at the command line. Then get back to me.

I have no interest in doing your first year homework vicariously.
Once again, I see no reason to think you understand what you are talking about, in fact, I see every reason to think otherwise. Link to something you have made with SQL and explain how you made it.
Anyway, I've modified the implementation of QuickSort in my own programming language to automatically measure the sortedness of the array before sorting it and print what would be the expected number of comparisons done by QuickSort according to the formula my genetic algorithm derived. From what I've seen, that formula usually overestimates the number of comparisons QuickSort will do on small arrays, sometimes by as much as two times. Of course, it works well for large arrays, because my genetic algorithm tweaked it using the measurements with large arrays.
Reply
#15
RE: C++ "sort"
Sometimes I am simply amazed at what text-editors can do. Notepad++ can export a syntax-highlighted code, together with the line numbers, into a RTF file (which can be opened by LibreOffice and Word). I've done that here. It's saved me a lot of time when writing my seminar.
Reply
#16
RE: C++ "sort"
I have no problem with someone getting under the hood and understanding what is going on there. In the world of line-of-business application development, though, you're working on a platform and most of the sort / search / indexing algorithms already "in the can" (in whatever framework you're using, .NET in my case) are "good enough" if not generally better than you could "naively" implement yourself.

For fun I did once build an AVL implementation of a b-tree. It is supposed to be faster to search an AVL tree, but slower to modify it, as it achieves its search speed by keeping itself perfectly balanced at all times. The implementation in .NET is hidden in classes like Dictionary<T> but happens to use the red-black algorithm, trading some lookup performance for better dynamic change speed. And that is in fact probably the right call for typical use cases. Recently though they added read-only versions of these dictionaries and lo and behold they use the AVL algorithm as the tradeoff is now different.

So in MY world, and the world in which most of the development jobs are, this stuff is of academic / personal curiosity interest, but seldom significantly improves the quality of what you can actually deliver.
Reply
#17
RE: C++ "sort"
Anyway, I've written the first version of my seminar, you can see it here. It's 23 pages of text, in Croatian.
Reply
#18
RE: C++ "sort"
Today, I've implemented MergeSort in AEC:
https://github.com/FlatAssembler/Arithme.../MergeSort
Reply
#19
RE: C++ "sort"
(December 15, 2019 at 3:33 pm)Abaddon_ire Wrote:
(December 15, 2019 at 1:41 pm)FlatAssembler Wrote: I wouldn't say it's stealing to continue someone's work. People who discovered an efficient algorithm don't own those algorithms, they existed before they were discovered in the same sense that the Pythagorean theorem existed before it was discovered: it exists in our world (and any world which approximately obeys the Euclidean Fifth Postulate) independently of whether it's discovered or not. And efficient sorting algorithms exist in all worlds in which a RAM machine is possible.
What do you mean you don't like Introsort? It's demonstrably the most efficient known algorithm for sorting large arrays that doesn't make assumptions about whether they are already partially or completely sorted.

Try writing SQL at the command line. Then get back to me.

I have no interest in doing your first year homework vicariously.

Lol try writing SQL from the command line? As your example of something more complicated than implementing and understanding the limiting behavior of sorting algorithms?

You, sir, are just a shitty troll.



@FlatAssembler

Understanding some of the more complicated sorting algorithms will help you in application development more by the means of understanding than the understanding itself. I am a Senior Developer with a medium sized data manipulation company. While my experience isn't exactly typical, I have used sorting a handful of times---and I have used built in/library functions every time. However, I can't tell you how valuable and worthwhile the time and knowledge was and is learning stuff like Big O notation and the memory organization and stack/heap use when learning in my algorithms class. That stuff is way more valuable, imo.
"There remain four irreducible objections to religious faith: that it wholly misrepresents the origins of man and the cosmos, that because of this original error it manages to combine the maximum servility with the maximum of solipsism, that it is both the result and the cause of dangerous sexual repression, and that it is ultimately grounded on wish-thinking." ~Christopher Hitchens, god is not Great

PM me your email address to join the Slack chat! I'll give you a taco(or five) if you join! --->There's an app and everything!<---
Reply
#20
RE: C++ "sort"
(December 29, 2019 at 10:27 am)SteelCurtain Wrote:
(December 15, 2019 at 3:33 pm)Abaddon_ire Wrote: Try writing SQL at the command line. Then get back to me.

I have no interest in doing your first year homework vicariously.

Lol try writing SQL from the command line? As your example of something more complicated than implementing and understanding the limiting behavior of sorting algorithms?

You, sir, are just a shitty troll.



@FlatAssembler

Understanding some of the more complicated sorting algorithms will help you in application development more by the means of understanding than the understanding itself. I am a Senior Developer with a medium sized data manipulation company. While my experience isn't exactly typical, I have used sorting a handful of times---and I have used built in/library functions every time. However, I can't tell you how valuable and worthwhile the time and knowledge was and is learning stuff like Big O notation and the memory organization and stack/heap use when learning in my algorithms class. That stuff is way more valuable, imo.

Tough. I have little time for first year assignments. It matters not how educated any of us may be, trying to lure others into doing ones homework is really, really shoddy no matter how one slices it.
Reply





Users browsing this thread: 1 Guest(s)