The Joy of Programming: qsort

I never write anything on here. Maybe I should add some of my random missives. So here’s today’s.

I’m not sure why, but I suddenly “needed” to see how qsort(3) was implemented.  Yikes.  I dunno what I was expecting but it wasn’t quite that; the closest was from the Unix V6/V7 source which is a simpler recursive mechanism (though still a bit more involved than I thought) but more recent versions are scary.  I suspect that the basic mechanism isn’t too brain-wrenching and maybe I’d be better off picking up one of my neglected tomes of Knuth’s The Art of Computer Programming or something of that ilk but the implementation looks hairy; probably as it’s several methodologies rolled into one, choosing the most appropriate based on size and what looks at a glance like interim results from the currently executing one.

It’s also interesting to compare the readability of the source code: Unix V6/V7 unsurprisingly use K&R C, with V6 not even using private variables; maybe they hadn’t been invented yet.  What was more surprising is that V10 is written in ANSI C.

Of the others, Minix (up to 3.1) is probably the easiest to read and understand, which is entirely unsurprising as that was the whole point; after that, Solaris was the most clearly written and copiously documented.  After that, NetBSD seems to have set the current standard with their implementation of Bentley & McIlroy’s Engineering a Sort Function, versions of which appear elsewhere including FreeBSD which surprisingly (to me, anyway) takes last place, the code being well and truly mangled not just with the plethora of #ifdef conditions but also the “huh?  Never heard of that before” block type, which had no further explanation, not even in the source.  So I had to resort to the always-reliable (ahem) Wikipedia which describes it as “a non-standard extension added by Apple Inc. to Clang‘s implementations of the C, C++, and Objective-C programming languages”.

Erm, righty-ho, then.  So I came here looking for something I was musing over while sat on the toilet that I presumed was quite straightforward and discovered that, not only is it not particularly, but Apple has added a non-standard extension to one of the most used programming languages that looks kinda like an obfuscated goto.

meh.  Maybe I should stick with writing bollocks on Twittarse.

Lawks a lordy, my bottom’s on fire!

Er… is this thing on?  One, two, one, two, testing…  (Why does everyone always use that same line when testing a mike?  Or a blog, or whatever?  How about something more novel and imaginative like “I am a little fishy who lives on the planet Zarg.  My name is Dave and so is my wife.  Wibble.”)