Advogato blog for fejjAdvogato blog for fejj5 Mar 2007- March 5, 2007 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...http://www.advogato.org/person/fejj/diary.html?start=177 4 Mar 2007- March 4, 2007 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...http://www.advogato.org/person/fejj/diary.html?start=176 4 Mar 2007- March 4, 2007 Like Merge Sort, Quick Sort promises O(n lg n) time in the average case, and, like Merge Sort, is also a recursive algorithm. However, it is important to be aware that Quick Sort is O(n n) worst case, where, ironically, the input is already mostly sorted in either direction. The way Quick Sort works is that it first chooses a pivot value with which to partition the working sequence into two segments. Next, it puts all items with values smaller than the pivot value into the first...http://www.advogato.org/person/fejj/diary.html?start=175 4 Mar 2007- March 4, 2007 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...http://www.advogato.org/person/fejj/diary.html?start=174 |