fejj is currently certified at Master level.

Name: Jeffrey Stedfast
Member since: 2000-06-14 21:57:47
Last Login: 2011-04-27 19:34:59

FOAF RDF Share This

Notes:

disclaimer: the thoughts expressed in my blog are none but mine own, they do not reflect the views of my employer.

Projects

Recent blog entries by fejj

Syndication: RSS 2.0

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

5 Mar 2007 (updated 6 Mar 2007 at 04:56 UTC) »
fzort: I think you mean Binary Insertion Sort and not Bubble Sort. The idea would be to use another in-place sorting algorithm that doesn't get hit hard when attempting to sort a segment that may already be pre-sorted. No reason to use anything slower than you have to, and so Binary Insertion Sort fits nicely.

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!

4 Mar 2007 (updated 4 Mar 2007 at 22:26 UTC) »

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.

4 Mar 2007 (updated 1 Apr 2011 at 19:43 UTC) »

Update: this article was moved: Quick Sort

4 Mar 2007 (updated 4 Mar 2007 at 14:50 UTC) »

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

174 older entries...

 

fejj certified others as follows:

  • fejj certified khemicals as Apprentice
  • fejj certified cael as Journeyer
  • fejj certified snippy as Apprentice
  • fejj certified mwh as Journeyer
  • fejj certified miguel as Master
  • fejj certified eliot as Apprentice
  • fejj certified roguemtl as Journeyer
  • fejj certified pavlov as Journeyer
  • fejj certified dexter as Apprentice
  • fejj certified vladimir as Journeyer
  • fejj certified harold as Journeyer
  • fejj certified itp as Master
  • fejj certified clahey as Journeyer
  • fejj certified jmecham as Apprentice
  • fejj certified mpav as Journeyer
  • fejj certified julian as Journeyer
  • fejj certified jacob as Master
  • fejj certified strlen as Apprentice
  • fejj certified nullity as Journeyer
  • fejj certified dto as Journeyer
  • fejj certified NetHunter as Journeyer
  • fejj certified rtmfd as Journeyer
  • fejj certified mjs as Master
  • fejj certified ian as Apprentice
  • fejj certified fejj as Master
  • fejj certified Jody as Master
  • fejj certified Radagast as Journeyer
  • fejj certified orph as Journeyer
  • fejj certified DraX as Apprentice
  • fejj certified needo as Apprentice
  • fejj certified federico as Master
  • fejj certified jrb as Master
  • fejj certified jpr as Journeyer
  • fejj certified ettore as Master
  • fejj certified rawb as Journeyer
  • fejj certified sopwith as Master
  • fejj certified raph as Master
  • fejj certified jdub as Journeyer
  • fejj certified msw as Master
  • fejj certified yosh as Master
  • fejj certified frb as Journeyer
  • fejj certified dtype as Master
  • fejj certified mikeszcz as Apprentice
  • fejj certified suso as Apprentice
  • fejj certified hadess as Journeyer
  • fejj certified campd as Journeyer
  • fejj certified chema as Journeyer
  • fejj certified bratsche as Journeyer
  • fejj certified raptor as Apprentice
  • fejj certified MikeGTN as Apprentice
  • fejj certified Telsa as Journeyer
  • fejj certified Iain as Journeyer
  • fejj certified rodrigo as Journeyer
  • fejj certified jfleck as Journeyer
  • fejj certified almer as Journeyer
  • fejj certified yakk as Master
  • fejj certified menesis as Journeyer
  • fejj certified nullspace as Apprentice
  • fejj certified gleblanc as Journeyer
  • fejj certified kwayne as Journeyer
  • fejj certified trow as Master
  • fejj certified menthos as Journeyer
  • fejj certified andersca as Master
  • fejj certified Hallski as Journeyer
  • fejj certified ishamael as Journeyer
  • fejj certified strath as Apprentice
  • fejj certified bdodson as Apprentice
  • fejj certified CEmery as Apprentice
  • fejj certified CharlesKerr as Master
  • fejj certified gabe as Journeyer
  • fejj certified gman as Master
  • fejj certified rml as Master
  • fejj certified toshok as Master
  • fejj certified maw as Apprentice
  • fejj certified fingolfin as Journeyer
  • fejj certified kz as Apprentice
  • fejj certified slamb as Apprentice
  • fejj certified harshy as Apprentice
  • fejj certified lewing as Master
  • fejj certified jlouis as Journeyer
  • fejj certified notzed as Master

Others have certified fejj as follows:

  • jae certified fejj as Journeyer
  • roguemtl certified fejj as Journeyer
  • listen certified fejj as Journeyer
  • cael certified fejj as Journeyer
  • temas certified fejj as Journeyer
  • mpav certified fejj as Journeyer
  • dexter certified fejj as Journeyer
  • julian certified fejj as Journeyer
  • khemicals certified fejj as Journeyer
  • NetHunter certified fejj as Journeyer
  • CelestialWizard certified fejj as Journeyer
  • rtmfd certified fejj as Journeyer
  • nullity certified fejj as Journeyer
  • moshez certified fejj as Journeyer
  • mjs certified fejj as Master
  • mwh certified fejj as Journeyer
  • bjc certified fejj as Apprentice
  • ishamael certified fejj as Master
  • ian certified fejj as Master
  • aaronl certified fejj as Journeyer
  • nixnut certified fejj as Journeyer
  • jonkare certified fejj as Journeyer
  • jbowman certified fejj as Journeyer
  • fejj certified fejj as Master
  • jtc certified fejj as Journeyer
  • sh certified fejj as Journeyer
  • piman certified fejj as Master
  • nosinut certified fejj as Journeyer
  • gleblanc certified fejj as Journeyer
  • Radagast certified fejj as Master
  • rossigee certified fejj as Journeyer
  • Stevey certified fejj as Journeyer
  • mikeszcz certified fejj as Journeyer
  • suso certified fejj as Journeyer
  • bratsche certified fejj as Journeyer
  • raptor certified fejj as Journeyer
  • MikeGTN certified fejj as Master
  • jfleck certified fejj as Master
  • almer certified fejj as Journeyer
  • yakk certified fejj as Master
  • menesis certified fejj as Master
  • khazad certified fejj as Journeyer
  • hadess certified fejj as Master
  • wardv certified fejj as Journeyer
  • nullspace certified fejj as Master
  • rodrigo certified fejj as Master
  • ignatz certified fejj as Master
  • fxn certified fejj as Master
  • Jody certified fejj as Master
  • menthos certified fejj as Journeyer
  • ebizo certified fejj as Journeyer
  • andersca certified fejj as Master
  • Hallski certified fejj as Master
  • gman certified fejj as Master
  • gabe certified fejj as Journeyer
  • cerquide certified fejj as Master
  • rkrishnan certified fejj as Master
  • Uraeus certified fejj as Journeyer
  • dobey certified fejj as Journeyer
  • badvogato certified fejj as Journeyer
  • strider certified fejj as Master
  • timur certified fejj as Master
  • rml certified fejj as Master
  • maw certified fejj as Master
  • dsandras certified fejj as Master
  • cinamod certified fejj as Master
  • kz certified fejj as Journeyer
  • fingolfin certified fejj as Master
  • notzed certified fejj as Journeyer
  • elanthis certified fejj as Master
  • rasjani certified fejj as Master
  • miah certified fejj as Master
  • brouhaha certified fejj as Master
  • harshy certified fejj as Master
  • ebf certified fejj as Master
  • alejandro certified fejj as Master
  • jlouis certified fejj as Journeyer
  • monkeyiq certified fejj as Master
  • clarkbw certified fejj as Master
  • riggwelter certified fejj as Master
  • marcos certified fejj as Master
  • lerdsuwa certified fejj as Master

[ Certification disabled because you're not logged in. ]

New Advogato Features

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!

X
Share this page