And here it is, your Moment of Zen:
Those who assume the worst in other people, are by their very nature among the worst people.
Those who assume the best in other people, are by their very nature among the best people.
-- Jeffrey Stedfast
Name: Jeffrey Stedfast
Member since: 2000-06-14 21:57:47
Last Login: 2011-04-27 19:34:59
Notes:
disclaimer: the thoughts expressed in my blog are none but mine own, they do not reflect the views of my employer.
And here it is, your Moment of Zen:
Those who assume the worst in other people, are by their very nature among the worst people.
Those who assume the best in other people, are by their very nature among the best people.
-- Jeffrey Stedfast
For historical reasons, a Binary Insertion Sort was probably also used to eliminate recursive function call overhead as well as stack overflows.
Note that while the binary search portion of the Binary Insertion Sort algorithm is recursive, since it is tail recursive, it can be implemented in such a way as to even avoid having to use an internal stack.
See the last implementation discussed here for an example on how to do that.
Thanks for the link too, btw, I will be sure to check that out later when I get home from work!
haruspex: Hence my comment above that line,
If your program makes heavy use of a sorting routine, you may want to consider implementing a tailored sort function rather than just using qsort().
By no means do I suggest writing your own low-level routines for no reason... but if your program is spending a lot of time sorting, then you might consider writing a tailored sort routine. Obviously this wouldn't make sense if sorting is barely even on the radar as far as time spent in your program.
Hopefully this clarifies my position and the intent of my wording (which I admit may have been unclear).
Note, also, that all of my entries in my blog series on sorting start off with an unoptimized version of the sort routine, implementing them as closely to the description of the algorithm as I can. From there, in each entry, I went on to describe my mode of thinking on how to achieve better performance (largely as an educational challenge to myself) - e.g. I never suggest pre-optimizing.
Update: more on sorting here.
Update: this article was moved: Quick Sort
I came across something cool the other day that I thought I'd share: a 25-byte long integer sort routine (that is to say, the routine itself is only 25 bytes long).
Here it is:
;--------------------------------------------------------------- ; Sorts an array of ints. C-callable (small model). 25 bytes. ; void sort (int n, int a[]); ; ; Courtesy of David Stafford. ;---------------------------------------------------------------.model small .code public _sort
top: mov dx,[bx] ; swap two adjacent ints xchg dx,[bx+2] xchg dx,[bx]
cmp dx,[bx] ; in the right order? jl top ; no, swap them back
inc bx ; go to the next integer inc bx loop top
_sort: pop dx ; get return address (entry point) pop cx ; get count pop bx ; get pointer push bx ; restore pointer dec cx ; decrement count push cx ; save count push dx ; save return address jg top ; if cx > 0
ret
end
fejj certified others as follows:
Others have certified fejj as follows:
[ Certification disabled because you're not logged in. ]
New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.
Keep up with the latest Advogato features by reading the Advogato status blog.
If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!