Re: Simple Sort - the smallest sorting routine?

Newsgroups	comp.lang.forth
Date	2013-07-07 21:58 -0700
References	(2 earlier) <f12bd478-60d3-4f51-a942-13022a83c8f0@googlegroups.com> <roKdnRgvKr7QzkTMnZ2dnUVZ_r2dnZ2d@supernews.com> <51d9665d$0$577$e4fe514c@dreader34.news.xs4all.nl> <3580755f-df77-4fb2-a441-931e4ddb6eb2@googlegroups.com> <ILudnXw1Gal-m0fMnZ2dnUVZ_r6dnZ2d@supernews.com>
Message-ID	<fc74ded2-c94e-45f8-a8c0-a2d860e0bd89@googlegroups.com> (permalink)
Subject	Re: Simple Sort - the smallest sorting routine?
From	hughaguilar96@yahoo.com

Show all headers | View raw

On Sunday, July 7, 2013 5:25:07 PM UTC-7, Andrew Haley wrote:
> hughaguilar96@yahoo.com wrote:
> > On Sunday, July 7, 2013 6:00:13 AM UTC-7, Albert van der Horst wrote:
> >> In article <roKdnRgvKr7QzkTMnZ2dnUVZ_r2dnZ2d@supernews.com>,
> >> Andrew Haley  <andrew29@littlepinkcloud.invalid> wrote:
> >> >hughaguilar96@yahoo.com wrote:
> >> >> On Saturday, July 6, 2013 6:38:38 AM UTC-7, Anton Ertl wrote:
> >> >>> >Median-of-3, if you really want to avoid the worst case.
> 
> >> >> Any algorithm that depends upon a prng, is something that I would avoid!
> 
> >> >Why?  Prejudice?
> 
> > Because it is all just luck --- not reproducible from one run to the next.
> 
> That really is not true, as you would know if you'd actually tried it.

A prng isn't based on luck? Luck is the definition of a prng!

The QuickSort is heavily dependent upon luck, as it needs to select a pivot that is pretty close to the median. The use of a prng in median-of-three selection just further luckifies this selection, to smooth over problem-patterns in the data such as presorting --- but the whole thing is just luck.

> > You don't measure anything either; you just read magazine articles
> > and believe everything that you're told.
> 
> And yet, astonishingly, I'm the one who actually produces the numbers.

Show us the source-code then.

> > Also, what processor were those tests done on?
> 
> Which part of
> Intel Core i5 M 480 @ 2.67GHz
> do you not understand?

As I said, x86 benchmarks are not worth much. There are a lot of factors that affect the speed of the x86. Preloading the code and data cache is a major factor. There are other factors --- the x86 is a very complicated processor --- it is not going to give consistent results on benchmarks. Also, benchmarks aren't a very good predictor of program speed, primarily because of the cache issue once again.

Anyway, this whole thread is getting ridiculous --- the comp.lang.forth clown army has gotten more riled up than usual --- an awful lot of emotional energy is getting burned up discussing sorting algorithms, which is quite remarkable considering that all of these sorting algorithms were invented decades ago (and not by any of us).

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Simple Sort - the smallest sorting routine? The Beez <the.beez.speaks@gmail.com> - 2013-06-25 13:12 -0700
  Re: Simple Sort - the smallest sorting routine? Mark Wills <markrobertwills@yahoo.co.uk> - 2013-06-25 23:48 -0700
    Re: Simple Sort - the smallest sorting routine? The Beez <the.beez.speaks@gmail.com> - 2013-06-26 09:11 -0700
  Re: Simple Sort - the smallest sorting routine? m.a.m.hendrix@tue.nl - 2013-06-26 02:03 -0700
  Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-06-26 11:25 -0500
    Re: Simple Sort - the smallest sorting routine? the_gavino_himself <visphatesjava@gmail.com> - 2013-06-26 12:36 -0700
      Re: Simple Sort - the smallest sorting routine? "Elizabeth D. Rather" <erather@forth.com> - 2013-06-26 09:49 -1000
    Re: Simple Sort - the smallest sorting routine? "WJ" <w_a_x_man@yahoo.com> - 2013-06-26 20:24 +0000
  Re: Simple Sort - the smallest sorting routine? "WJ" <w_a_x_man@yahoo.com> - 2013-06-26 20:23 +0000
    Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-06-26 13:35 -0700
      Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-06-26 16:37 -0700
        Re: Simple Sort - the smallest sorting routine? The Beez <the.beez.speaks@gmail.com> - 2013-06-27 01:31 -0700
          Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-06-27 04:04 -0500
          Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-06-30 09:27 -0700
            Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-06-30 13:23 -0700
            Re: Simple Sort - the smallest sorting routine? "Alex McDonald" <blog@rivadpm.com> - 2013-06-30 21:48 +0100
              Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-06-30 16:53 -0700
                Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-01 04:34 -0700
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-03 18:41 -0700
                Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-04 02:58 -0700
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-04 21:30 -0700
                Re: Simple Sort - the smallest sorting routine? "Alex McDonald" <blog@rivadpm.com> - 2013-07-06 00:18 +0100
                Re: Simple Sort - the smallest sorting routine? Bernd Paysan <bernd.paysan@gmx.de> - 2013-07-06 13:45 +0200
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-06 07:49 -0500
                Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-06 13:38 +0000
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-06 10:06 -0500
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-06 23:08 -0700
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-07 06:24 -0500
                Re: Simple Sort - the smallest sorting routine? Bernd Paysan <bernd.paysan@gmx.de> - 2013-07-07 23:47 +0200
                Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-07 09:59 +0000
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-07 06:52 -0500
                Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-07 12:18 +0000
                Re: Simple Sort - the smallest sorting routine? m.a.m.hendrix@tue.nl - 2013-07-08 00:06 -0700
                Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-08 09:50 +0000
                Re: Simple Sort - the smallest sorting routine? m.a.m.hendrix@tue.nl - 2013-07-08 03:14 -0700
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-08 09:53 -0500
                Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-09 14:25 +0000
                Re: Simple Sort - the smallest sorting routine? Bernd Paysan <bernd.paysan@gmx.de> - 2013-07-09 23:39 +0200
                Re: Simple Sort - the smallest sorting routine? Paul Rubin <no.email@nospam.invalid> - 2013-07-09 18:03 -0700
                Re: Simple Sort - the smallest sorting routine? Bernd Paysan <bernd.paysan@gmx.de> - 2013-07-10 23:05 +0200
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 03:21 -0500
                Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-10 10:29 +0000
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 05:44 -0500
                Re: Simple Sort - the smallest sorting routine? Paul Rubin <no.email@nospam.invalid> - 2013-07-10 04:07 -0700
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 06:06 -0500
                Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-10 14:21 +0000
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 04:45 -0500
                Re: Simple Sort - the smallest sorting routine? Paul Rubin <no.email@nospam.invalid> - 2013-07-10 03:13 -0700
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 05:09 -0500
                Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-10 12:16 +0000
                Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-10 10:38 +0000
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 06:45 -0500
                Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-10 13:56 +0000
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-10 10:54 -0700
                Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-10 13:57 -0700
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 07:15 -0500
                Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-10 13:52 +0000
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 15:00 -0500
                Re: Simple Sort - the smallest sorting routine? Coos Haak <chforth@hccnet.nl> - 2013-07-10 16:13 +0200
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 17:07 -0500
                Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-11 10:53 +0000
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-11 10:40 -0700
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-11 15:17 -0500
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-11 16:54 -0700
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-12 03:07 -0500
                Re: Simple Sort - the smallest sorting routine? Bernd Paysan <bernd.paysan@gmx.de> - 2013-07-07 00:43 +0200
                Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-07 00:21 +0000
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-06 20:32 -0700
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-07 06:38 -0500
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-07 07:05 -0500
                Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-07 13:00 +0000
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-07 09:47 -0700
                Re: Simple Sort - the smallest sorting routine? "Alex McDonald" <blog@rivadpm.com> - 2013-07-07 21:22 +0100
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-07 19:25 -0500
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-07 21:58 -0700
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-08 02:27 -0500
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-08 21:18 -0700
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-09 04:20 -0500
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-10 10:30 -0700
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 15:13 -0500
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-10 13:57 -0700
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 16:57 -0500
                Re: Simple Sort - the smallest sorting routine? Elizabeth D Rather <erather@forth.com> - 2013-07-10 13:00 -1000
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-10 22:19 -0700
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-11 10:23 -0700
                Re: Simple Sort - the smallest sorting routine? Bernd Paysan <bernd.paysan@gmx.de> - 2013-07-11 01:12 +0200
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-11 00:33 -0500
                Re: Simple Sort - the smallest sorting routine? Bernd Paysan <bernd.paysan@gmx.de> - 2013-07-11 11:48 +0200
                Re: Simple Sort - the smallest sorting routine? Paul Rubin <no.email@nospam.invalid> - 2013-07-11 03:08 -0700
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-11 05:00 -0500
                Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-11 10:17 +0000
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-11 06:53 -0500
                Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-11 15:21 +0000
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-11 10:37 -0500
                Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-11 17:07 +0000
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-11 15:19 -0500
                Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-11 17:33 +0000
                Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-11 18:18 +0000
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-11 16:46 -0700
                Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-12 03:48 -0700
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-12 10:55 -0700
                Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-12 19:29 +0000
                Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-15 09:50 +0000
                Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-12 13:22 -0700
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-13 20:05 -0700
                Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-14 11:34 +0000
                Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-14 09:18 -0700
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-14 16:05 -0700
                Re: Simple Sort - the smallest sorting routine? Ron Aaron <rambamist@gmail.com> - 2013-07-15 06:12 +0300
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-14 22:17 -0700
                Re: Simple Sort - the smallest sorting routine? Ron Aaron <rambamist@gmail.com> - 2013-07-15 11:44 +0300
                Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-15 09:42 -0700
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-16 18:03 -0700
                Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-17 00:54 -0700
                Re: Simple Sort - the smallest sorting routine? Howerd <howerdo@yahoo.co.uk> - 2013-07-14 10:09 -0700
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-14 15:35 -0700
                Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-11 17:08 +0000
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-11 15:30 -0500
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-11 09:34 -0700
                Re: Simple Sort - the smallest sorting routine? Michael Morris <morrimichael@gmail.com> - 2013-07-15 23:09 -0500
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-16 17:46 -0700
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-17 03:14 -0500
                Re: Simple Sort - the smallest sorting routine? "Rod Pemberton" <do_not_have@notemailnotq.cpm> - 2013-07-17 21:47 -0400
                Re: Simple Sort - the smallest sorting routine? "Alex McDonald" <blog@rivadpm.com> - 2013-07-11 04:06 +0100
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-06 20:18 -0700
                Re: Simple Sort - the smallest sorting routine? "Alex McDonald" <blog@rivadpm.com> - 2013-07-07 16:48 +0100
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-07 09:13 -0700
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-07 09:13 -0700
                Re: Simple Sort - the smallest sorting routine? "Alex McDonald" <blog@rivadpm.com> - 2013-07-07 21:24 +0100
                Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-04 14:41 +0000
        Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-06-27 01:59 -0700
          Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-06-30 09:30 -0700
            Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-06-30 12:59 -0700
    Re: Simple Sort - the smallest sorting routine? awegel@arcor.de (Alex Wegel) - 2013-06-27 00:08 +0200
    Re: Simple Sort - the smallest sorting routine? Doug Hoffman <glidedog@gmail.com> - 2013-06-26 19:31 -0400
      Re: Simple Sort - the smallest sorting routine? Doug Hoffman <glidedog@gmail.com> - 2013-06-27 06:26 -0400
  Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-06-28 02:05 +0000
    Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-04 07:33 -0700
      Re: Simple Sort - the smallest sorting routine? Coos Haak <chforth@hccnet.nl> - 2013-07-05 00:47 +0200
        Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-14 19:01 +0000
          Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-15 01:28 +0000
        Re: Simple Sort - the smallest sorting routine? Ian Osgood <iano@quirkster.com> - 2013-07-19 11:29 -0700
  Re: Simple Sort - the smallest sorting routine? Brad Eckert <hwfwguy@gmail.com> - 2013-07-19 09:09 -0700

csiph-web