Question about which tools to use, bugs, the best way to implement a function, etc should go here. Don't forget to see if your question is answered in the wiki first! When in doubt post here.
What exactly do you mean with insertion sort? In-placed? Curious does PDCLib qsort do merging?
I went through a big pile of bugs before I got my inplaced merge-sort-add algorithm just right. But it was written in assembly and you know how ugly it can get with fair amount of conditional jumps. :-X
I would post it up but several things that is holding me back like fixing up the old commented code, and its also written in masm which I know a lot of you don't use (also ported to C in VC6.0 project that doesn't seem to be popular around here). It uses a loop rather then recursive, so doesn't use much stack (roughly the 6 register pushed onto stack and 16 bytes of local variables per call). Still, there are some exceptions that need to recurse no more then once where I have implemented a list -> list mapping. Not that anyone cares, but its quite the weight off my shoulders.
While I agree with you insofar as software should be correct and rugged even when given bogus input, there is a line somewhere. Even if you assert() every PUSH() and POP() in qsort(), the real danger in that function is in the caller passing bogus parameters, and you cannot assert() that with all the care in the world.
And, performance is a design goal in itself. Asserting stuff that cannot fail might look smart, but really isn't. As long as you made damn sure that it cannot fail, like I failed to do with that qsort(). (Like several dozen others who copied Raymond's code, too, which isn't a good excuse really.)
Every good solution is obvious once you've found it.
Ryu wrote:
What exactly do you mean with insertion sort? In-placed? Curious does PDCLib qsort do merging?
The code is on the SourceForge page, the link is in my signature.
I honestly didn't bother much with the implementation, I copied it from available PD sources, reformatted it to the PDCLib standards, and added a couple of test cases to make sure it doesn't garble your data. I considered that "good enough" for now, but as I said before, getting unstable at 28 elements isn't "good enough", it's bogus, and will get fixed in the next pre-release. (Teaches me to copy&paste other people's sources - qsort() being the only function where I did that in PDCLib.)
It uses a loop rather then recursive, so doesn't use much stack...
Same with PDCLib. The qsort() is implemented iterative with a static stack. (And it will remain that way, for performance considerations.)
Every good solution is obvious once you've found it.
Asserts disappear in production code anyway (compiled with "-D NDEBUG -O2") so I don't worry about them impacting performance. Any tests which really hit performance really badly will go inside "#if (PARANOIA)" in my code.
Ahh... now I see where you're coming from with those asserts.
Well, I'm satisfied with the if-conditional surrounding the POP() - I didn't deem it necessary to add any checks to the PUSHes because of {see above}. Anyway, no assert() would have caught the error in question, as I didn't have any large-enough test run on the function.
Again, thanks for pointing it out.
Every good solution is obvious once you've found it.
/* We swap first with middle element, then sort that with second
and last element so that eventually first element is the median
of the three - avoiding pathological pivots.
TODO: Instead of middle element, chose one randomly.
*/
You have nothing to worry. Median of first/last/middle should be enough.
Solar wrote:
(Isn't it strange how many things get addressed in a what-if manner over code that's readily available for checking yourself? </funny sarcasm>)
But by answering my question instead of re-directing me to the code, you've increased my productivity by 500%! ;D
Top three reasons why my OS project died:
Too much overtime at work
Got married
My brain got stuck in an infinite loop while trying to design the memory manager
Solar: I know where to find the source, my nature as always been to find something interesting about it or something that can be potiently useful both in developement and learning curve before taking a peek at others source code. I may end up there possibly when someone switch my cup of coffee with a cup of hot chocolate.
Warning: Exposure of contents within this forum may suddenly find lost of time, may prevent you from your daily routines, may cause a space out and have algebra notations floating around your head and can happend anywhere. This may lead to bad sleeping habbits or eating disorder, and cause dizzyness, tiredness or drinking too much caffeine.
I could pass on all typos / grammar errors in your post, but I have to correct this one:
Ryu wrote:
...drinking too much caffeine.
No such thing. ;D
Besides, being instructional is one of the design goals of the PDCLib - i.e., being as little obfuscated as possible. (I agree it got a bit fuzzy in _PDCLIB_int.h, but it was the only way I could think of to keep _PDCLIB_config.h as small and redundancy-free as it is.)
Every good solution is obvious once you've found it.
Try both yawning and not being able to keep your eyes open, whilst shaking from an overdose caffeine intended to fight the first problem. Yes, there is a thing as too much caffeine. No, it's not within reachability for most mortals (and if you did, you might prove yourself mortal).
Human limit for caffeine is about 4 grams. Coffee contains about 80mg per cup (average). That means that if you take 50 cups of coffee and upkeep (what your body tears down while you're drinking) you'd probably end up in the hospital.
I had dropped the issue for some time to focus on stdio. Now I returned to fix the qsort(), and I finally found out how that 20-entry stack came to pass...
Read any paper on the Quicksort algorithm, and you will find a mention of Quicksort requiring "log(n) additional stack space".
log( 2^64 ) == 20.
The problem is that this is for the average case. As is quite well-known, Quicksort has a weakness that can result in O(n^2) behaviour - which a 20-element stack cannot handle.
All the more surprising that the code I based PDCLib's qsort() on is found so widespread on the internet...
Every good solution is obvious once you've found it.
