Path: csiph.com!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups: comp.lang.c++
Subject: Re: C++ threshold for "stupid" sorting algorithms (O(n^2))
Date: Sun, 05 Jan 2020 22:26:05 +0000
Organization: A noiseless patient Spider
Lines: 24
Message-ID: <87pnfxlev6.fsf@bsb.me.uk>
References: <qui2k6$rst$1@dont-email.me> <qui33j$3m0$1@news.albasani.net> <87y2urozdn.fsf@bsb.me.uk> <qurj51$fv8$1@news.albasani.net> <8736cumt3s.fsf@bsb.me.uk> <quroia$31g$1@news.albasani.net> <87v9pqkoyz.fsf@bsb.me.uk> <qusq7e$us$1@news.albasani.net>
Mime-Version: 1.0
Content-Type: text/plain
Injection-Info: reader02.eternal-september.org; posting-host="b6adbb1a8cdffb0b3cbd084d31d6cb15"; logging-data="30261"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX192MLYvPymIOmIcru+OWxmkp13rrChM4Pc="
Cancel-Lock: sha1:5YUsCXRacZWSxhPpruTuCADLtnU= sha1:OqAUN0dQ9h6Oh+hoIgwFxzk5B1M=
X-BSB-Auth: 1.b2240492b011dce40d20.20200105222605GMT.87pnfxlev6.fsf@bsb.me.uk
Xref: csiph.com comp.lang.c++:71159

Bonita Montero <Bonita.Montero@gmail.com> writes:

>>>> Second, the results from your timing code will depend on the data as
>>>> well as on the algorithm.  For example, on my laptop, with sorted data,
>>>> your code (slightly modified to use non-random numbers) shows bubble
>>>> sort as faster (by a factor of at least 2) for all sizes tested (you
>>>> go up to 20). ...
>
>>> That's not true. You're a liar.
>
>> That's a nasty thing to say.  If I thought you were a serious
>> contributer, I'd be offended.
>
> Try the fixed code. The fixed code gives this with gcc on my computer:

No apology for accusing me of lying I see.

The fixed code does not alter what I said: the simple sort is faster for
all your test sizes for some data sets -- specifically when the data are
already sorted.  The factor is now smaller (no longer always greater
than 2) but still between 1.5 and 2.

-- 
Ben.