Qsort.h – Quicksort as a C macro (2019)
github.com
Qsort.h – Quicksort as a C macro (2019)
1–10 of 50 posts
Re: Qsort.h – Quicksort as a C macro (2019)
#2The link to Sedgewick's 1978 paper no longer works, but an archive of it can be found here: http://web.archive.org/web/20190713031319/http://penguin.ewu...
Re: Qsort.h – Quicksort as a C macro (2019)
#3This is very good: it uses the original Hoare partitioning algorithm which moves two indices at opposite ends of the array partition toward each other, rather than the ill-considered Lomuto partitioning:
while (1) { \
do q_i++; while (Q_LESS(q_i, q_l)); \
do q_j--; while (Q_LESS(q_l, q_j)); \
if (q_i >= q_j) break; /* Sedgewick says "until j Lomuto ends up performing more comparisons.
What's more, Lomuto has quadratic behavior for sequences that are just repetitions of a value: every partitioning and sub-partitioning is a degenerate case. Hoare's algorithm deftly avoids this problem. You can explain that using the above snippet. If all elements are the same, then Q_LESS(q_i, q_l) is always false. Thus each of the two do/while loops executes one unconditional iteration, so that the two indices q_i and q_j march toward each other and meet in the middle. The repeating sequence thus nicely cut in half, and recursively so, ensuring O(N log N) behavior.
You can't easily banish the worst case from Quicksort, but implementations should not exhibit worst case behavior on inputs that have some obvious pattern, like a repeated value.
Re: Qsort.h – Quicksort as a C macro (2019)
#4The link to Sedgewick's 1978 paper no longer works, but an archive of it can be found here: http://web.archive.org/web/20190713031319/http://penguin.ewu...
The paper says that more detailed discussion of partition methods is given in [15]. That looks like Sedwicks's Ph. D thesis which was on Quicksort?
I found this: https://sedgewick.io/wp-content/themes/sedgewick/papers/1975...
Basically a longer book on Quicksort with a lot more analysis.
He doesn't discuss any partitioning methods that do not move two indices toward each other from opposite ends of the subarray. It's not even on the table.
Re: Qsort.h – Quicksort as a C macro (2019)
#5The link to Sedgewick's 1978 paper no longer works, but an archive of it can be found here: http://web.archive.org/web/20190713031319/http://penguin.ewu...
The paper says that more detailed discussion of partition methods is given in [15]. That looks like Sedwicks's Ph. D thesis which was on Quicksort? I found this: https://sedgewick.io/wp-content/themes/sedgewick/papers/1975... Basically a longer book on Quicksort with a lot more analysis. He doesn't discuss any partitioning methods that do not move two indices toward each other from opposite ends of the subarray. It's…
Of course the logo on the paper title page is a sequence of 8 lines with each doubling on thickness.
Though it'd be more visually and intuitively accurate if the lines started large and cut in half each step. :P
Re: Qsort.h – Quicksort as a C macro (2019)
#6If you're doing metaprogramming using the C preprocessor, it's time to move to a more advanced language.
Re: Qsort.h – Quicksort as a C macro (2019)
#7If you're doing metaprogramming using the C preprocessor, it's time to move to a more advanced language.
I knew someone would come up with this kind of "wisdom". For starters you do not know what other languages they might be using for development. And whatever they do they definitely do not need patronizing.
Re: Qsort.h – Quicksort as a C macro (2019)
#8If you're doing metaprogramming using the C preprocessor, it's time to move to a more advanced language.
I knew someone would come up with this kind of "wisdom". For starters you do not know what other languages they might be using for development. And whatever they do they definitely do not need patronizing.
I've done a share of C metaprogramming with the preprocessor myself, and have dealt a lot with other peoples' C metaprogramming.
I've also seen people use pages of algrebra as a substitute for a couple lines of calculus.
I struggled for years with a soldering iron, always frustrated by bad solder joints. Then, I discovered a Weller thermostat controlled iron, and get a perfect joint every time.
Not everyone knows there are better ways to do things.
Re: Qsort.h – Quicksort as a C macro (2019)
#9Earlier quoted context omitted.
I knew someone would come up with this kind of "wisdom". For starters you do not know what other languages they might be using for development. And whatever they do they definitely do not need patronizing.
I've done a share of C metaprogramming with the preprocessor myself, and have dealt a lot with other peoples' C metaprogramming. I've also seen people use pages of algrebra as a substitute for a couple lines of calculus. I struggled for years with a soldering iron, always frustrated by bad solder joints. Then, I discovered a Weller thermostat controlled iron, and get a perfect joint every time. Not everyone knows the…
Your experience soldering is a much better response. You present a concrete suggestion for use a weller thermostat controlled iron. But you did not present a concrete suggestion for an alternative to the C pre-processor.
You could do this with C++ templates, for instance. But the LESS and SWAP operations may or may not get inlined. With the C pre-processor you can be certain that the operations get inlined, since no other alternative interpretation is available to the compiler.
Re: Qsort.h – Quicksort as a C macro (2019)
#10If you're doing metaprogramming using the C preprocessor, it's time to move to a more advanced language.
Maybe they don't want to move to a more advanced language, maybe they want to mess around with the C preprocessor. :)