Kjell Rilbe skrev:
Vlad Khorsun skrev:
In a similar vein, if Firebird is still using the venerable Quick Sort
that a coded more or less straight from Knuth, Volume 2, in 1984, see
Bentley & McIlroy's "Engineering a Sort Function" for a must faster
version. If anyone is interested, I've turned it into a C++ template,
which I'd be happy to contribute.
There is even better algorithm
http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628
Interesting idea. :-) I like it! Wonder if it would be even more
efficient to use K pivots where K is some fixed fraction or
logarithmic fraction >= 1 of the number N of elements to be sorted?
For each recursion, the array to be sorted is smaller, and a smaller
number of pivots is used. Then the "if not, then swap them" would be
generalized to "sort the pivots", which could actually also be done
using a recursive call to the sorting algorithm.
Maybe someone with time and the appropriate skills could do the math
to find the theoretical properties of such an algorithm and also try
it out in practice?
Perhaps not such a novel idea as I thought. :-)
http://cs.stanford.edu/~rishig/courses/ref/l11a.pdf
But seems to talk about fixed K = 3 as opposed to a dynamic K as I suggest.
Kjell
--
DataDIA logotyp
Kjell Rilbe
Telefon: 08-761 06 55
Mobil: 0733-44 24 64
DataDIA AB
Ulvsundavägen 106
168 67 Bromma
www.datadia.se <http://www.datadia.se>
08-514 905 90
Företagskontakt.se <http://xn--fretagskontakt-vpb.se> - urval av företag
och kontaktinformation
Personkontakt.se <http://personkontakt.se> - urval av hushållsadresser
------------------------------------------------------------------------------
Meet PCI DSS 3.0 Compliance Requirements with EventLog Analyzer
Achieve PCI DSS 3.0 Compliant Status with Out-of-the-box PCI DSS Reports
Are you Audit-Ready for PCI DSS 3.0 Compliance? Download White paper
Comply to PCI DSS 3.0 Requirement 10 and 11.5 with EventLog Analyzer
http://pubads.g.doubleclick.net/gampad/clk?id=154622311&iu=/4140/ostg.clktrk
Firebird-Devel mailing list, web interface at
https://lists.sourceforge.net/lists/listinfo/firebird-devel
