The issue is often the cost of each step rather than the worst case number
of steps. In the final analysis implementations need to be measured over a
set of compilers rather comparison of the algorithms.
On Tuesday, September 23, 2014, Kjell Rilbe <kjell.rilbe.konto...@datadia.se>
wrote:
> 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
> --
>
> [image: 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
> 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
>
--
Jim Starkey
------------------------------------------------------------------------------
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
