Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #71131
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Newsgroups | comp.lang.c++ |
| Subject | Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) |
| Date | 2020-01-05 04:20 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <8736cumt3s.fsf@bsb.me.uk> (permalink) |
| References | <qui2k6$rst$1@dont-email.me> <qui33j$3m0$1@news.albasani.net> <87y2urozdn.fsf@bsb.me.uk> <qurj51$fv8$1@news.albasani.net> |
Bonita Montero <Bonita.Montero@gmail.com> writes: >>>> In your experience, what is (roughly) a reasonable threshold (n) in >>>> terms of convenience of passing from stupid algorithms (bubblesort, >>>> gnomesort) to better and more complex ones ? > >>> Don't use the simpler algorithms. Algthough they might be faster >>> on a few elements, their runtime doesn't count then because there >>> are just a few elements. > >> But there might be billions of such small sorts. It's a rare situation, >> but it shows that the logic you used is not sound. > > Try this on your computer. First, I was commenting on your logic, not your conclusion. Your conclusion -- don't use simple but slow sorts -- might be right but you can't get to that conclusion using the logic you used. 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). I don't know if the code is measuring this correctly -- I am just reporting on the output. Third, the OP was not just about bubble sort. To get a sound answer from measurements, the best simple sort, insertion sort, should be used. <cut timing code> -- Ben.
Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
C++ threshold for "stupid" sorting algorithms (O(n^2)) Soviet_Mario <SovietMario@CCCP.MIR> - 2020-01-01 13:17 +0100
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-01 13:25 +0100
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-01-01 17:33 +0000
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-05 03:54 +0100
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-05 04:04 +0100
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2020-01-05 03:59 +0000
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-05 05:03 +0100
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Soviet_Mario <SovietMario@CCCP.MIR> - 2020-01-05 21:13 +0100
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-06 05:50 +0100
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-06 06:55 +0100
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-01-05 04:20 +0000
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-05 05:26 +0100
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-01-05 13:33 +0000
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-05 15:01 +0100
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-01-05 22:26 +0000
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-06 05:39 +0100
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Öö Tiib <ootiib@hot.ee> - 2020-01-05 23:54 -0800
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-06 08:59 +0100
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Öö Tiib <ootiib@hot.ee> - 2020-01-06 01:02 -0800
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Jorgen Grahn <grahn+nntp@snipabacken.se> - 2020-01-06 09:34 +0000
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-06 10:36 +0100
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Öö Tiib <ootiib@hot.ee> - 2020-01-06 03:33 -0800
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-06 12:59 +0100
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-01-06 22:54 +0000
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-07 04:57 +0100
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Melzzzzz <Melzzzzz@zzzzz.com> - 2020-01-07 07:51 +0000
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Melzzzzz <Melzzzzz@zzzzz.com> - 2020-01-05 15:16 +0000
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-05 05:50 +0100
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bo Persson <bo@bo-persson.se> - 2020-01-01 13:34 +0100
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Soviet_Mario <SovietMario@CCCP.MIR> - 2020-01-01 14:09 +0100
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bo Persson <bo@bo-persson.se> - 2020-01-01 15:16 +0100
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Robert Wessel <robertwessel2@yahoo.com> - 2020-01-01 09:24 -0600
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Soviet_Mario <SovietMario@CCCP.MIR> - 2020-01-01 17:12 +0100
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Öö Tiib <ootiib@hot.ee> - 2020-01-02 15:11 -0800
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-01-10 13:53 -0800
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Robert Wessel <robertwessel2@yahoo.com> - 2020-01-10 16:45 -0600
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-01-21 03:11 -0800
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-01-21 15:04 +0000
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-01-27 11:52 -0800
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-01-30 00:32 +0000
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-02-15 05:30 -0800
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-02-15 16:39 +0000
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Christian Gollwitzer <auriocus@gmx.de> - 2020-01-02 11:28 +0100
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Soviet_Mario <SovietMario@CCCP.MIR> - 2020-01-02 19:46 +0100
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-02 20:00 +0100
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-03 07:37 +0100
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Soviet_Mario <SovietMario@CCCP.MIR> - 2020-01-03 20:06 +0100
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Öö Tiib <ootiib@hot.ee> - 2020-01-03 11:12 -0800
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Soviet_Mario <SovietMario@CCCP.MIR> - 2020-01-04 17:58 +0100
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) David Brown <david.brown@hesbynett.no> - 2020-01-03 21:25 +0100
Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Melzzzzz <Melzzzzz@zzzzz.com> - 2020-01-03 21:00 +0000
csiph-web