Groups > comp.lang.c > #147130 > unrolled thread

Challenge for Feeb: dealing with large numbers in C

Started by	DFS <nospam@dfs.com>
First post	2019-10-20 18:12 -0400
Last post	2019-10-29 15:15 +0100
Articles	20 on this page of 114 — 19 participants

Back to article view | Back to comp.lang.c

  Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-20 18:12 -0400
    Re: Challenge for Feeb: dealing with large numbers in C Barry Schwarz <schwarzb@delq.com> - 2019-10-20 18:33 -0700
      Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-20 23:16 -0400
        Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-21 13:15 +0100
          Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-21 14:40 -0400
            Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-22 00:54 +0100
              Re: Challenge for Feeb: dealing with large numbers in C David Brown <david.brown@hesbynett.no> - 2019-10-22 10:05 +0200
              Re: Challenge for Feeb: dealing with large numbers in C Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-10-23 07:18 -0700
            Re: Challenge for Feeb: dealing with large numbers in C Manfred <noname@invalid.add> - 2019-10-26 20:01 +0200
              Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-26 17:50 -0400
                Re: Challenge for Feeb: dealing with large numbers in C Manfred <noname@add.invalid> - 2019-10-28 16:33 +0100
        Re: Challenge for Feeb: dealing with large numbers in C Barry Schwarz <schwarzb@delq.com> - 2019-10-21 07:56 -0700
        Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-21 16:46 +0100
          Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-21 14:57 -0400
            Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-21 20:53 +0100
              Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-21 16:05 -0400
                Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-21 21:12 +0100
              Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-21 20:08 -0400
                Re: Challenge for Feeb: dealing with large numbers in C David Brown <david.brown@hesbynett.no> - 2019-10-22 10:27 +0200
            Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-22 19:45 +0100
              Re: Challenge for Feeb: dealing with large numbers in C Eli the Bearded <*@eli.users.panix.com> - 2019-10-22 19:58 +0000
              Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-23 11:46 -0400
                Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-23 20:02 +0100
                Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-24 01:38 +0100
                  Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-23 22:10 -0400
                    Re: Challenge for Feeb: dealing with large numbers in C Ike Naar <ike@sdf.lonestar.org> - 2019-10-24 07:24 +0000
                      Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-24 09:29 -0400
                        Re: Challenge for Feeb: dealing with large numbers in C James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-10-24 08:45 -0700
                          Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-24 11:56 -0400
                            Re: Challenge for Feeb: dealing with large numbers in C Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-24 09:13 -0700
                              Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-24 18:28 +0100
                    Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-24 10:36 +0100
                    Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-24 09:26 -0400
                      Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-24 18:29 +0100
                        Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-24 14:38 -0400
                          Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-24 21:30 +0100
                  Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-24 11:30 +0100
                    Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-24 20:36 +0100
                      Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-24 21:34 +0100
                        Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-24 22:42 +0100
                      Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-24 18:59 -0400
                        Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-25 02:48 +0100
                        Re: Challenge for Feeb: dealing with large numbers in C Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-26 04:33 -0700
                          Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-26 17:21 +0100
                            Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-26 18:47 +0100
                              Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-26 23:24 +0100
                                Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-27 00:29 +0100
                                  Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-27 01:58 +0100
                                    Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-27 12:02 +0000
                                      Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 02:08 +0000
                            Re: Challenge for Feeb: dealing with large numbers in C Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2019-10-26 14:29 -0600
                              Re: Challenge for Feeb: dealing with large numbers in C Keith Thompson <kst-u@mib.org> - 2019-10-26 13:36 -0700
                              Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-26 22:06 +0100
                              Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-26 23:04 +0100
                            Re: Challenge for Feeb: dealing with large numbers in C David Brown <david.brown@hesbynett.no> - 2019-10-27 12:49 +0100
                              Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-27 18:20 +0000
                                Re: Challenge for Feeb: dealing with large numbers in C David Brown <david.brown@hesbynett.no> - 2019-10-27 22:45 +0100
                                  Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 00:08 +0000
                                Re: Challenge for Feeb: dealing with large numbers in C Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-27 14:57 -0700
                                  Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 01:08 +0000
                                    Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-28 01:44 +0000
                                      Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 02:31 +0000
                                        Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-28 10:42 +0000
                                          Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-28 12:45 +0000
                                          Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 17:39 +0000
                                            Re: Challenge for Feeb: dealing with large numbers in C David Brown <david.brown@hesbynett.no> - 2019-10-28 20:31 +0100
                                              Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 20:22 +0000
                                                Re: Challenge for Feeb: dealing with large numbers in C David Brown <david.brown@hesbynett.no> - 2019-10-28 22:07 +0100
                                                  Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 22:22 +0000
                                                    Re: Challenge for Feeb: dealing with large numbers in C David Brown <david.brown@hesbynett.no> - 2019-10-29 10:17 +0100
                                                      Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-29 11:21 +0000
                                      Re: Challenge for Feeb: dealing with large numbers in C already5chosen@yahoo.com - 2019-10-28 11:05 -0700
                                        Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-28 19:26 +0000
                                          Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 21:08 +0000
                                            Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-28 21:57 +0000
                                              Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 23:59 +0000
                                                Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 00:53 +0000
                                                  Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-29 01:09 +0000
                                                    Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 01:32 +0000
                                                      Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-28 22:44 -0400
                                                      Re: Challenge for Feeb: dealing with large numbers in C Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-29 03:05 -0700
                                                        Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 11:12 +0000
                                                        Re: Challenge for Feeb: dealing with large numbers in C already5chosen@yahoo.com - 2019-10-29 04:19 -0700
                                                          Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 11:47 +0000
                                                            Re: Challenge for Feeb: dealing with large numbers in C Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-29 05:03 -0700
                                                              Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 13:16 +0000
                                                            Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-29 17:13 +0000
                                                              Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 17:35 +0000
                                                        Re: Challenge for Feeb: dealing with large numbers in C Ike Naar <ike@sdf.lonestar.org> - 2019-10-30 07:19 +0000
                                                      Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-29 16:19 +0000
                                                        Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 16:50 +0000
                                                          Re: Challenge for Feeb: dealing with large numbers in C Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-29 10:03 -0700
                                                            Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 17:13 +0000
                                                            Re: Challenge for Feeb: dealing with large numbers in C already5chosen@yahoo.com - 2019-10-29 10:23 -0700
                                                              Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-29 22:20 +0000
                                                                Re: Challenge for Feeb: dealing with large numbers in C already5chosen@yahoo.com - 2019-10-30 03:04 -0700
                                                                  Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-30 15:39 +0000
                                                                    Re: Challenge for Feeb: dealing with large numbers in C Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-30 09:02 -0700
                                                                      Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-30 19:35 +0000
                                                                    Re: Challenge for Feeb: dealing with large numbers in C already5chosen@yahoo.com - 2019-10-30 14:11 -0700
                                                                      Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-31 03:34 +0000
                                    Re: Challenge for Feeb: dealing with large numbers in C Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-04 17:02 -0800
                        Re: Challenge for Feeb: dealing with large numbers in C Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2019-10-26 12:30 -0400
                          Re: Challenge for Feeb: dealing with large numbers in C Robert Wessel <robertwessel2@yahoo.com> - 2019-10-26 12:03 -0500
                            Re: Challenge for Feeb: dealing with large numbers in C Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2019-10-26 14:25 -0600
                      Re: Challenge for Feeb: dealing with large numbers in C Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-10-24 18:06 -0700
          Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-21 22:44 +0100
            Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-21 19:00 -0400
    Re: Challenge for Feeb: dealing with large numbers in C Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2019-10-21 10:20 +0800
      Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-21 12:44 +0100
    Re: Challenge for Feeb: dealing with large numbers in C Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2019-10-21 10:24 +0800
      Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-20 23:05 -0400
        Re: Challenge for Feeb: dealing with large numbers in C Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2019-10-21 11:32 +0800
    Re: Challenge for Feeb: dealing with large numbers in C Autist <autist69@gmail.com> - 2019-10-29 15:15 +0100

Page 4 of 6 — ← Prev page 1 2 3 [4] 5 6 Next page →

#147301

From	Bart <bc@freeuk.com>
Date	2019-10-28 01:44 +0000
Message-ID	<lKrtF.1173925$Nw3.180880@fx40.am4>
In reply to	#147300

On 28/10/2019 01:08, Ben Bacarisse wrote:
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

>> Next lesson is other sort methods the students can devise themselves,
>> which will usually be O(N^2) algorithms, and a discussion of the advantages
>> and disadvantages. So you are teaching that some algorithms are better
>> than others in different circumstances.
> 
> All good provided (a) bubble sort isn't taught unless it comes up as a
> student-devised algorithm, and (b) the students understand that there
> are no situations in which bubble sort would be the best choice.  In
> practice the problem is that, after taking some courses, the students
> /can't/ choose because they can't remember any other algorithm than the
> not-really-bubble-sort that's being discussed here.
> 
> A key outcome should be that the students understand that insertion sort
> is the best choice when a simple quadratic algorithm will do.  They
> should be able to come up with this:
> 
>    for (int i = 1; i < n; i++)
>      for (int j = i; j > 0 && A[j-1] > A[j]; j--)
>        swap(&A[j-1], &A[j]);
> 
> as easily as the dreaded quasi bubble sort.  It's not hard -- all the
> bounds are logical.

I've just tried the famous insertion sort; the first algorithm I saw 
online (adapted from what I guess was 0-based to 1-based) was this:

   proc isort(a)=
       for i:=2 to a.len do
           value:=a[i]
           holepos:=i
           while holepos>1 and a[holepos-1]>value do
               a[holepos]:=a[holepos-1]
               --holepos
           od

           a[holepos]:=value
      od
   end

This has a somewhat different inner loop than yours. It turns out to be 
about 4 times as fast as my bubble sort for the same random data, in the 
same language and for larger data sets.

However, if I was sorting data for which that timing was important, I'd 
use a quick-sort routine. Or some other approach entirely if I knew the 
data lent itself to that.

So I don't actually use bubble sort for real tasks (other than as 
benchmarks), but if I did need something quick (quick to write) it's 
what I would use.

Interpreted bubble-sort sorts 5000 numbers in about 1 second, while the 
above insertion sort does it in 0.4 seconds, with the differences 
narrowing rapidly for smaller data. But my qsort (still interpreted) can 
sort nearly 1000000 numbers in 1 second.

[toc] | [prev] | [next] | [standalone]

#147303

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Date	2019-10-28 02:31 +0000
Message-ID	<87y2x5r47n.fsf@bsb.me.uk>
In reply to	#147301

Bart <bc@freeuk.com> writes:

> On 28/10/2019 01:08, Ben Bacarisse wrote:

>> A key outcome should be that the students understand that insertion sort
>> is the best choice when a simple quadratic algorithm will do.  They
>> should be able to come up with this:
>>
>>    for (int i = 1; i < n; i++)
>>      for (int j = i; j > 0 && A[j-1] > A[j]; j--)
>>        swap(&A[j-1], &A[j]);
>>
>> as easily as the dreaded quasi bubble sort.  It's not hard -- all the
>> bounds are logical.
>
> I've just tried the famous insertion sort; the first algorithm I saw
> online (adapted from what I guess was 0-based to 1-based) was this:
>
>   proc isort(a)=
>       for i:=2 to a.len do
>           value:=a[i]
>           holepos:=i
>           while holepos>1 and a[holepos-1]>value do
>               a[holepos]:=a[holepos-1]
>               --holepos
>           od
>
>           a[holepos]:=value
>      od
>   end

> This has a somewhat different inner loop than yours.

That's a more complex (but more efficient) version than the swapping
one.  The swapping one is good for weaning people off bubble sort
because it's only three lines of C and is still more efficient.

> It turns out to be about 4 times as fast as my bubble sort for the
> same random data, in the same language and for larger data sets.

And it will be very much faster for almost sorted data -- one of points
that Malcolm raised in favour of bubble sort which your sort does not
have.

> However, if I was sorting data for which that timing was important,
> I'd use a quick-sort routine.

Quick sort has a high overhead for small arrays so almost all the good
implementations of fast sorting switch to insertion sort when the
recursion has produced small partitions.  The speed-up is worth it
because the recursion will result in a very large number of small array
sorts.

> So I don't actually use bubble sort for real tasks (other than as
> benchmarks), but if I did need something quick (quick to write) it's
> what I would use.

My point, all along, has been that insertion sort is quick to write
provided students are aware of how it can written simply.

> Interpreted bubble-sort sorts 5000 numbers in about 1 second, while
> the above insertion sort does it in 0.4 seconds, with the differences
> narrowing rapidly for smaller data. But my qsort (still interpreted)
> can sort nearly 1000000 numbers in 1 second.

It would be interesting to see what that comes down to if you switch to
insertion sort for small partitions.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#147304

From	Bart <bc@freeuk.com>
Date	2019-10-28 10:42 +0000
Message-ID	<LCztF.910712$aq7.468058@fx09.am4>
In reply to	#147303

On 28/10/2019 02:31, Ben Bacarisse wrote:
> Bart <bc@freeuk.com> writes:

> 
>> Interpreted bubble-sort sorts 5000 numbers in about 1 second, while
>> the above insertion sort does it in 0.4 seconds, with the differences
>> narrowing rapidly for smaller data. But my qsort (still interpreted)
>> can sort nearly 1000000 numbers in 1 second.
> 
> It would be interesting to see what that comes down to if you switch to
> insertion sort for small partitions.

Not much as it turns out. Sorting a 1M-element array of random integers 
goes from 0.8 to 0.78 seconds [this excludes array generation time], if 
using my insertion sort for partitions of 10 or fewer elements.

(A slightly different version, using list-slicing instead of passing 
explicit partition bounds, showed a bigger difference (0.94 to 0.8), but 
was slower overall: https://github.com/sal55/qx/blob/master/qsort.q)

It might be different if using a tight, static language.

[toc] | [prev] | [next] | [standalone]

#147305

From	Bart <bc@freeuk.com>
Date	2019-10-28 12:45 +0000
Message-ID	<OpBtF.2$hk3.0@fx19.am4>
In reply to	#147304

On 28/10/2019 10:42, Bart wrote:
> On 28/10/2019 02:31, Ben Bacarisse wrote:
>> Bart <bc@freeuk.com> writes:
> 
>>
>>> Interpreted bubble-sort sorts 5000 numbers in about 1 second, while
>>> the above insertion sort does it in 0.4 seconds, with the differences
>>> narrowing rapidly for smaller data. But my qsort (still interpreted)
>>> can sort nearly 1000000 numbers in 1 second.
>>
>> It would be interesting to see what that comes down to if you switch to
>> insertion sort for small partitions.
> 
> Not much as it turns out. Sorting a 1M-element array of random integers 
> goes from 0.8 to 0.78 seconds [this excludes array generation time], if 
> using my insertion sort for partitions of 10 or fewer elements.
> 
> (A slightly different version, using list-slicing instead of passing 
> explicit partition bounds, showed a bigger difference (0.94 to 0.8), but 
> was slower overall: https://github.com/sal55/qx/blob/master/qsort.q)
> 
> It might be different if using a tight, static language.
> 

A version in C is given below. You can experiment with the threshold of 
64 inside qsort2(), but I also found it make only a small difference 
using the test code given (ie. all-random data).

(gcc-O3 on this code (using T=int32 or T=int64 on N=10M) was pretty much 
10 times as fast as my interpreted code, which is not bad for dynamic 
code. Tcc was only 5 times as fast, and gcc=O0 4.5 times. I think main 
memory access is factor here.)

----------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

enum {N=10000000};
//enum {N=100000};
typedef int T;

void isort(T *a, int n) {
     T value;
     int holepos;

     for (int i=1; i<n; ++i) {
         value=a[i];
         holepos=i;
         while (holepos>0 && a[holepos-1]>value) {
             a[holepos]=a[holepos-1];
             --holepos;
         }
         a[holepos]=value;
     }
}

void qsort2(T *a, int ll, int rr) {
     int i,j;
     T pivot, temp;

     if (rr-ll+1<=64) {
         isort(a+ll,rr-ll+1);
         return;
     }

     i=ll;
     j=rr;
     pivot=a[(ll+rr)/2];

     do {
         while (pivot>a[i] && i<rr) ++i;
         while (pivot<a[j] && j>ll) --j;
         if (i<=j) {
             temp=a[i]; a[i]=a[j]; a[j]=temp;
             ++i;
             --j;
         }
     } while (i<=j);

     if (ll<j) qsort2(a,ll,j);
     if (i<rr) qsort2(a,i,rr);
}

void myqsort(T *a, int n) {qsort2(a,0,n-1);}

int issorted(T *a,int n) {
     for (int i=0; i<n-1; ++i) {
         if (a[i]>a[i+1]) return 0;
     }
     return 1;
}

int main(void) {
     T *a = malloc(N*sizeof(T));
     int t;

     for (int i=0; i<N; ++i) a[i]=rand();

     t=clock();
     myqsort(a,N);
     t=clock()-t;

     printf("Issorted(A) = %s\n",(issorted(a,N)?"Yes":"No"));
     printf("Time = %d ticks\n",t);
}
----------------------------------------------------

[toc] | [prev] | [next] | [standalone]

#147307

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Date	2019-10-28 17:39 +0000
Message-ID	<87o8y0rcq2.fsf@bsb.me.uk>
In reply to	#147304

Bart <bc@freeuk.com> writes:

> On 28/10/2019 02:31, Ben Bacarisse wrote:
>> Bart <bc@freeuk.com> writes:
>
>>
>>> Interpreted bubble-sort sorts 5000 numbers in about 1 second, while
>>> the above insertion sort does it in 0.4 seconds, with the differences
>>> narrowing rapidly for smaller data. But my qsort (still interpreted)
>>> can sort nearly 1000000 numbers in 1 second.
>>
>> It would be interesting to see what that comes down to if you switch to
>> insertion sort for small partitions.
>
> Not much as it turns out. Sorting a 1M-element array of random
> integers goes from 0.8 to 0.78 seconds [this excludes array generation
> time], if using my insertion sort for partitions of 10 or fewer
> elements.

Thanks.  Like so many things to do with timing, this might be one of
those that has been dramatically altered by modern memory architectures.
And it obviously depends on the exact code.

I was interested enough to try myself and I got a 10% reduction for
large arrays of 32-but ints, with the sweet spot for switching at around
60.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#147310

From	David Brown <david.brown@hesbynett.no>
Date	2019-10-28 20:31 +0100
Message-ID	<qp7fmc$k0m$1@dont-email.me>
In reply to	#147307

On 28/10/2019 18:39, Ben Bacarisse wrote:
> Bart <bc@freeuk.com> writes:
> 
>> On 28/10/2019 02:31, Ben Bacarisse wrote:
>>> Bart <bc@freeuk.com> writes:
>>
>>>
>>>> Interpreted bubble-sort sorts 5000 numbers in about 1 second, while
>>>> the above insertion sort does it in 0.4 seconds, with the differences
>>>> narrowing rapidly for smaller data. But my qsort (still interpreted)
>>>> can sort nearly 1000000 numbers in 1 second.
>>>
>>> It would be interesting to see what that comes down to if you switch to
>>> insertion sort for small partitions.
>>
>> Not much as it turns out. Sorting a 1M-element array of random
>> integers goes from 0.8 to 0.78 seconds [this excludes array generation
>> time], if using my insertion sort for partitions of 10 or fewer
>> elements.
> 
> Thanks.  Like so many things to do with timing, this might be one of
> those that has been dramatically altered by modern memory architectures.
> And it obviously depends on the exact code.
> 

I remember reading a paper about this, suggesting that the "big O" in 
operation count is a poor indicator of performance on modern systems, 
and that the most important factor is minimising cache thrashing.


> I was interested enough to try myself and I got a 10% reduction for
> large arrays of 32-but ints, with the sweet spot for switching at around
> 60.
>

[toc] | [prev] | [next] | [standalone]

#147311

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Date	2019-10-28 20:22 +0000
Message-ID	<87imo8r56n.fsf@bsb.me.uk>
In reply to	#147310

David Brown <david.brown@hesbynett.no> writes:

> On 28/10/2019 18:39, Ben Bacarisse wrote:
>> Bart <bc@freeuk.com> writes:
>>
>>> On 28/10/2019 02:31, Ben Bacarisse wrote:
>>>> Bart <bc@freeuk.com> writes:
>>>
>>>>
>>>>> Interpreted bubble-sort sorts 5000 numbers in about 1 second, while
>>>>> the above insertion sort does it in 0.4 seconds, with the differences
>>>>> narrowing rapidly for smaller data. But my qsort (still interpreted)
>>>>> can sort nearly 1000000 numbers in 1 second.
>>>>
>>>> It would be interesting to see what that comes down to if you switch to
>>>> insertion sort for small partitions.
>>>
>>> Not much as it turns out. Sorting a 1M-element array of random
>>> integers goes from 0.8 to 0.78 seconds [this excludes array generation
>>> time], if using my insertion sort for partitions of 10 or fewer
>>> elements.
>>
>> Thanks.  Like so many things to do with timing, this might be one of
>> those that has been dramatically altered by modern memory architectures.
>> And it obviously depends on the exact code.
>>
>
> I remember reading a paper about this, suggesting that the "big O" in
> operation count is a poor indicator of performance on modern systems,
> and that the most important factor is minimising cache thrashing.

What an odd remark.  Asymptotic bounds on operation counts were never a
good indicator of performance.  Do you remember anything more that could
identify the author?

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#147312

From	David Brown <david.brown@hesbynett.no>
Date	2019-10-28 22:07 +0100
Message-ID	<qp7lbf$onf$1@dont-email.me>
In reply to	#147311

On 28/10/2019 21:22, Ben Bacarisse wrote:
> David Brown <david.brown@hesbynett.no> writes:
> 
>> On 28/10/2019 18:39, Ben Bacarisse wrote:
>>> Bart <bc@freeuk.com> writes:
>>>
>>>> On 28/10/2019 02:31, Ben Bacarisse wrote:
>>>>> Bart <bc@freeuk.com> writes:
>>>>
>>>>>
>>>>>> Interpreted bubble-sort sorts 5000 numbers in about 1 second, while
>>>>>> the above insertion sort does it in 0.4 seconds, with the differences
>>>>>> narrowing rapidly for smaller data. But my qsort (still interpreted)
>>>>>> can sort nearly 1000000 numbers in 1 second.
>>>>>
>>>>> It would be interesting to see what that comes down to if you switch to
>>>>> insertion sort for small partitions.
>>>>
>>>> Not much as it turns out. Sorting a 1M-element array of random
>>>> integers goes from 0.8 to 0.78 seconds [this excludes array generation
>>>> time], if using my insertion sort for partitions of 10 or fewer
>>>> elements.
>>>
>>> Thanks.  Like so many things to do with timing, this might be one of
>>> those that has been dramatically altered by modern memory architectures.
>>> And it obviously depends on the exact code.
>>>
>>
>> I remember reading a paper about this, suggesting that the "big O" in
>> operation count is a poor indicator of performance on modern systems,
>> and that the most important factor is minimising cache thrashing.
> 
> What an odd remark.  Asymptotic bounds on operation counts were never a
> good indicator of performance.  Do you remember anything more that could
> identify the author?
> 

Big O operation counts is often taken as an indication of performance 
scaling (to be more accurate than my first remark).  In terms of 
operation counts alone, an O(n.log n) algorithm will be faster than an 
O(n²) algorithm for big enough n.  It is not uncommon for people to 
taken into account the scaling of memory space too.  But the point of 
the paper's author is that cache usage - the hit and miss rates - can 
easily be more important than the operations that are usually counted 
(typically compares and swaps, for a sorting algorithm).

I suppose cache effects won't change the asymptotic behaviour, since you 
can only have a cache miss in combination with an operation, but it can 
be very significant when comparing algorithms with the same asymptotic 
operation counts, or when working with data sets that are not /that/ big.

[toc] | [prev] | [next] | [standalone]

#147315

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Date	2019-10-28 22:22 +0000
Message-ID	<877e4oqzm2.fsf@bsb.me.uk>
In reply to	#147312

David Brown <david.brown@hesbynett.no> writes:

> On 28/10/2019 21:22, Ben Bacarisse wrote:
>> David Brown <david.brown@hesbynett.no> writes:
>>
>>> On 28/10/2019 18:39, Ben Bacarisse wrote:
>>>> Bart <bc@freeuk.com> writes:
>>>>
>>>>> On 28/10/2019 02:31, Ben Bacarisse wrote:
>>>>>> Bart <bc@freeuk.com> writes:
>>>>>
>>>>>>
>>>>>>> Interpreted bubble-sort sorts 5000 numbers in about 1 second, while
>>>>>>> the above insertion sort does it in 0.4 seconds, with the differences
>>>>>>> narrowing rapidly for smaller data. But my qsort (still interpreted)
>>>>>>> can sort nearly 1000000 numbers in 1 second.
>>>>>>
>>>>>> It would be interesting to see what that comes down to if you switch to
>>>>>> insertion sort for small partitions.
>>>>>
>>>>> Not much as it turns out. Sorting a 1M-element array of random
>>>>> integers goes from 0.8 to 0.78 seconds [this excludes array generation
>>>>> time], if using my insertion sort for partitions of 10 or fewer
>>>>> elements.
>>>>
>>>> Thanks.  Like so many things to do with timing, this might be one of
>>>> those that has been dramatically altered by modern memory architectures.
>>>> And it obviously depends on the exact code.
>>>>
>>>
>>> I remember reading a paper about this, suggesting that the "big O" in
>>> operation count is a poor indicator of performance on modern systems,
>>> and that the most important factor is minimising cache thrashing.
>>
>> What an odd remark.  Asymptotic bounds on operation counts were never a
>> good indicator of performance.  Do you remember anything more that could
>> identify the author?
>>
>
> Big O operation counts is often taken as an indication of performance
> scaling (to be more accurate than my first remark).  In terms of
> operation counts alone, an O(n.log n) algorithm will be faster than an
> O(n²) algorithm for big enough n.  It is not uncommon for people to
> taken into account the scaling of memory space too.  But the point of
> the paper's author is that cache usage - the hit and miss rates - can
> easily be more important than the operations that are usually counted
> (typically compares and swaps, for a sorting algorithm).
>
> I suppose cache effects won't change the asymptotic behaviour, since
> you can only have a cache miss in combination with an operation, but
> it can be very significant when comparing algorithms with the same
> asymptotic operation counts, or when working with data sets that are
> not /that/ big.

I can't work out what it is the paper is saying.  Is there nothing more
you remember about it that could help me find it?  A stab-in-the-dark
search throws up

https://lemire.me/blog/2013/07/11/big-o-notation-and-real-world-performance/

which might, at a pinch, be a blog post by the same author.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#147323

From	David Brown <david.brown@hesbynett.no>
Date	2019-10-29 10:17 +0100
Message-ID	<qp9035$r8h$1@dont-email.me>
In reply to	#147315

On 28/10/2019 23:22, Ben Bacarisse wrote:
> David Brown <david.brown@hesbynett.no> writes:
> 
>> On 28/10/2019 21:22, Ben Bacarisse wrote:
>>> David Brown <david.brown@hesbynett.no> writes:
>>>
>>>> On 28/10/2019 18:39, Ben Bacarisse wrote:
>>>>> Bart <bc@freeuk.com> writes:
>>>>>
>>>>>> On 28/10/2019 02:31, Ben Bacarisse wrote:
>>>>>>> Bart <bc@freeuk.com> writes:
>>>>>>
>>>>>>>
>>>>>>>> Interpreted bubble-sort sorts 5000 numbers in about 1 second, while
>>>>>>>> the above insertion sort does it in 0.4 seconds, with the differences
>>>>>>>> narrowing rapidly for smaller data. But my qsort (still interpreted)
>>>>>>>> can sort nearly 1000000 numbers in 1 second.
>>>>>>>
>>>>>>> It would be interesting to see what that comes down to if you switch to
>>>>>>> insertion sort for small partitions.
>>>>>>
>>>>>> Not much as it turns out. Sorting a 1M-element array of random
>>>>>> integers goes from 0.8 to 0.78 seconds [this excludes array generation
>>>>>> time], if using my insertion sort for partitions of 10 or fewer
>>>>>> elements.
>>>>>
>>>>> Thanks.  Like so many things to do with timing, this might be one of
>>>>> those that has been dramatically altered by modern memory architectures.
>>>>> And it obviously depends on the exact code.
>>>>>
>>>>
>>>> I remember reading a paper about this, suggesting that the "big O" in
>>>> operation count is a poor indicator of performance on modern systems,
>>>> and that the most important factor is minimising cache thrashing.
>>>
>>> What an odd remark.  Asymptotic bounds on operation counts were never a
>>> good indicator of performance.  Do you remember anything more that could
>>> identify the author?
>>>
>>
>> Big O operation counts is often taken as an indication of performance
>> scaling (to be more accurate than my first remark).  In terms of
>> operation counts alone, an O(n.log n) algorithm will be faster than an
>> O(n²) algorithm for big enough n.  It is not uncommon for people to
>> taken into account the scaling of memory space too.  But the point of
>> the paper's author is that cache usage - the hit and miss rates - can
>> easily be more important than the operations that are usually counted
>> (typically compares and swaps, for a sorting algorithm).
>>
>> I suppose cache effects won't change the asymptotic behaviour, since
>> you can only have a cache miss in combination with an operation, but
>> it can be very significant when comparing algorithms with the same
>> asymptotic operation counts, or when working with data sets that are
>> not /that/ big.
> 
> I can't work out what it is the paper is saying.  Is there nothing more
> you remember about it that could help me find it?  A stab-in-the-dark
> search throws up
> 
> https://lemire.me/blog/2013/07/11/big-o-notation-and-real-world-performance/
> 
> which might, at a pinch, be a blog post by the same author.
> 

That blog post does not ring a bell.

When I said a "paper", I did not specifically mean an academic paper,
but a more general "something someone wrote".  I can't remember any
useful details, or the format - it was merely something I came across on
the internet somewhere, a good while ago.  It might have been an
academic paper, a blog post, a web page, an article in an online
publication, etc.  And I don't know who wrote it, or what their
qualifications might have been.

I am afraid I don't have references or even a good idea of the content
of the article I read.

All I can tell you is that when I read it, it struck me as interesting
to see how big an effect caching had in the run-time of algorithms like
sorting, which was not an aspect that had been covered in my algorithm
design courses many years ago.

[toc] | [prev] | [next] | [standalone]

#147327

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Date	2019-10-29 11:21 +0000
Message-ID	<87imo7pzjr.fsf@bsb.me.uk>
In reply to	#147323

David Brown <david.brown@hesbynett.no> writes:
<cut>
> I am afraid I don't have references or even a good idea of the content
> of the article I read.
>
> All I can tell you is that when I read it, it struck me as interesting
> to see how big an effect caching had in the run-time of algorithms like
> sorting, which was not an aspect that had been covered in my algorithm
> design courses many years ago.

Just knowing it addressed the run-time of sorting will help narrow the
search.  Thanks.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#147308

From	already5chosen@yahoo.com
Date	2019-10-28 11:05 -0700
Message-ID	<44a985ee-1d94-4af9-8a38-124c57cc0a4f@googlegroups.com>
In reply to	#147301

On Monday, October 28, 2019 at 3:44:59 AM UTC+2, Bart wrote:
> On 28/10/2019 01:08, Ben Bacarisse wrote:
> > Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
> 
> >> Next lesson is other sort methods the students can devise themselves,
> >> which will usually be O(N^2) algorithms, and a discussion of the advantages
> >> and disadvantages. So you are teaching that some algorithms are better
> >> than others in different circumstances.
> > 
> > All good provided (a) bubble sort isn't taught unless it comes up as a
> > student-devised algorithm, and (b) the students understand that there
> > are no situations in which bubble sort would be the best choice.  In
> > practice the problem is that, after taking some courses, the students
> > /can't/ choose because they can't remember any other algorithm than the
> > not-really-bubble-sort that's being discussed here.
> > 
> > A key outcome should be that the students understand that insertion sort
> > is the best choice when a simple quadratic algorithm will do.  They
> > should be able to come up with this:
> > 
> >    for (int i = 1; i < n; i++)
> >      for (int j = i; j > 0 && A[j-1] > A[j]; j--)
> >        swap(&A[j-1], &A[j]);
> > 
> > as easily as the dreaded quasi bubble sort.  It's not hard -- all the
> > bounds are logical.
> 
> I've just tried the famous insertion sort; the first algorithm I saw 
> online (adapted from what I guess was 0-based to 1-based) was this:
> 
>    proc isort(a)=
>        for i:=2 to a.len do
>            value:=a[i]
>            holepos:=i
>            while holepos>1 and a[holepos-1]>value do
>                a[holepos]:=a[holepos-1]
>                --holepos
>            od
> 
>            a[holepos]:=value
>       od
>    end
> 
> This has a somewhat different inner loop than yours. It turns out to be 
> about 4 times as fast as my bubble sort for the same random data, in the 
> same language and for larger data sets.
> 
> However, if I was sorting data for which that timing was important, I'd 
> use a quick-sort routine. Or some other approach entirely if I knew the 
> data lent itself to that.
> 


Count-based sorting algorithms sort arrays of millions of random 32-bit or 64-bit integers many times faster than quicksort. It does not make quicksort useless.
The same apply to quicksort vs straight insertion sort.
Sometimes (big records, quick comparisons) the same applies to straight insertion sort vs direct selection sort.
The same *never* apply to  straight insertion sort vs bubblesort.

Ben is simply correct in everything he said. And you are simply stubborn for no reason.


> So I don't actually use bubble sort for real tasks (other than as 
> benchmarks), but if I did need something quick (quick to write) it's 
> what I would use.
> 
> Interpreted bubble-sort sorts 5000 numbers in about 1 second, while the 
> above insertion sort does it in 0.4 seconds, with the differences 
> narrowing rapidly for smaller data. But my qsort (still interpreted) can 
> sort nearly 1000000 numbers in 1 second.

[toc] | [prev] | [next] | [standalone]

#147309

From	Bart <bc@freeuk.com>
Date	2019-10-28 19:26 +0000
Message-ID	<BhHtF.1932$Fr3.640@fx39.am4>
In reply to	#147308

On 28/10/2019 18:05, already5chosen@yahoo.com wrote:
> On Monday, October 28, 2019 at 3:44:59 AM UTC+2, Bart wrote:

>> This has a somewhat different inner loop than yours. It turns out to be
>> about 4 times as fast as my bubble sort for the same random data, in the
>> same language and for larger data sets.
>>
>> However, if I was sorting data for which that timing was important, I'd
>> use a quick-sort routine. Or some other approach entirely if I knew the
>> data lent itself to that.
>>
> 
> 
> Count-based sorting algorithms sort arrays of millions of random 32-bit or 64-bit integers many times faster than quicksort.

That sounds like what I meant by 'some other approach entirely if I knew 
the data lent itself to that'. (And like the histogram method posted in 
the thread.)

>It does not make quicksort useless.

Quicksort, insertion sort etc are general purpose algorithms that will 
work with any values of data. (Although they can also be used with a 
user-supplied compare function to sort a table of indices, when the 
sorting has to be across parallel sets of data.)

> The same apply to quicksort vs straight insertion sort.
> Sometimes (big records, quick comparisons) the same applies to straight insertion sort vs direct selection sort.
> The same *never* apply to  straight insertion sort vs bubblesort.
> 
> Ben is simply correct in everything he said. And you are simply stubborn for no reason.

I just have a soft soft for bubble sort; the way it works, the way the 
action is always localised, is aesthetically pleasing.

It just has a slightly lower threshold at which it stops being viable 
than insertion sort, and a much lower threshold than quicksort.

In the same way that interpreted languages have a certain threshold at 
which the task to be accomplished will be more practical in compiled 
code. Or the magnitudes of bignum where a simple library will become too 
slow compared with a sophisticated one.

In my own code, general purpose sort is used rarely as I would use other 
techniques like the ones alluded to above.

BTW, I posted a quicksort routine earlier that sorted 10 million random 
numbers in about 1 second. I can use a counting technique to reduce to 
50msec (20 times faster), since I know the range of numbers is 0 to 
RAND_MAX (0 to 32767 on my machine). However, I don't consider this a 
general purpose sort:

-------------------------------------

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

enum {N=10000000};
typedef long long int T;

void ccsort(T *a, int n) {
     int *counts = malloc((RAND_MAX+1)*sizeof(int));
     int k,m;

     memset(counts,0,(RAND_MAX+1)*sizeof(int));
     for (int i=0; i<n; ++i) {
         ++counts[a[i]];
     }

     k=0;
     for (int i=0; i<=RAND_MAX; ++i) {
         m=counts[i];
         while (m--) {
             a[k++]=i;
         }
     }
}

int issorted(T *a,int n) {
     for (int i=0; i<n-1; ++i) {
         if (a[i]>a[i+1]) return 0;
     }
     return 1;
}

int main(void) {
     T *a = malloc(N*sizeof(T));
     int t;

     for (int i=0; i<N; ++i) a[i]=rand();

     t=clock();
     ccsort(a,N);
     t=clock()-t;

     printf("Issorted(A) = %s N=%d\n",(issorted(a,N)?"Yes":"No"),N);
     printf("Time = %d ticks\n",t);
}

[toc] | [prev] | [next] | [standalone]

#147313

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Date	2019-10-28 21:08 +0000
Message-ID	<87d0egr31l.fsf@bsb.me.uk>
In reply to	#147309

Bart <bc@freeuk.com> writes:

> I just have a soft soft for bubble sort; the way it works, the way the
> action is always localised, is aesthetically pleasing.

I will re-iterate that what you call bubble sort is this:

  for (int i = 0; i < n; i++)
     for (int j = 1; j < n; j++)
        if (a[j-1] > a[j])
           swap(&a[j-1], a&[j]);

You praise the way the action is always localised but it is also
localised in this version of insertion sort:

  for (int i = 1; i < n; i++)
     for (int j = i; j > 0 && a[j-1] > a[j]; j--)
        swap(&a[j-1], &a[j]);

so you will, no doubt, praise that too, yes?

You like the way the first works, even with its frequent pointless tests
when the data is already sorted (or almost sorted), but /I/ like the
fact that the second detects this condition and back out early with no
extra code or flags (unlike the real bubble sort that needs both).
Don't you like that about how insertion sort works?

All that's left is aesthetics, and in that department the second
algorithm wins hands down for me, but that's harder to argue.

> It just has a slightly lower threshold at which it stops being viable
> than insertion sort,

You may remember Malcolm's original remark about frequently having to
sort short collections of almost-sorted data.  Even a small extra cost
might be significant when the operation is done often enough.  The
algorithm you are championing does n*(n-1) compares /every time/, even
when the data are sorted.  The second code does n-1 compares on sorted
data.  So that's only 80 more compares on a 10-elements array, or 361
more if there are 20 elements, but why pay that price when the second
code is so simple and so elegant?

I think your criteria for code elegance are jumbled.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#147314

From	Bart <bc@freeuk.com>
Date	2019-10-28 21:57 +0000
Message-ID	<1vJtF.1857$om6.1719@fx27.am4>
In reply to	#147313

On 28/10/2019 21:08, Ben Bacarisse wrote:
> Bart <bc@freeuk.com> writes:
> 
>> I just have a soft soft for bubble sort; the way it works, the way the
>> action is always localised, is aesthetically pleasing.
> 
> I will re-iterate that what you call bubble sort is this:
> 
>    for (int i = 0; i < n; i++)

I think n-1 will do here.

>       for (int j = 1; j < n; j++)
>          if (a[j-1] > a[j])
>             swap(&a[j-1], a&[j]);
> 
> You praise the way the action is always localised but it is also
> localised in this version of insertion sort:
> 
>    for (int i = 1; i < n; i++)
>       for (int j = i; j > 0 && a[j-1] > a[j]; j--)
>          swap(&a[j-1], &a[j]);
> 
> so you will, no doubt, praise that too, yes?

Yes, but it seems insertion can be written in more diverse ways. I've 
already said bubble-sort is more consistent.

The main deviation is whether to opt to finish early, which would be a 
good idea if data might already be nearly sorted.

> You like the way the first works, even with its frequent pointless tests
> when the data is already sorted (or almost sorted), but /I/ like the
> fact that the second detects this condition and back out early with no
> extra code or flags (unlike the real bubble sort that needs both).
> Don't you like that about how insertion sort works?
> 
> All that's left is aesthetics, and in that department the second
> algorithm wins hands down for me, but that's harder to argue.
> 
>> It just has a slightly lower threshold at which it stops being viable
>> than insertion sort,
> 
> You may remember Malcolm's original remark about frequently having to
> sort short collections of almost-sorted data.  Even a small extra cost
> might be significant when the operation is done often enough.  The
> algorithm you are championing does n*(n-1) compares /every time/, even
> when the data are sorted.  The second code does n-1 compares on sorted
> data.  So that's only 80 more compares on a 10-elements array, or 361
> more if there are 20 elements, but why pay that price when the second
> code is so simple and so elegant?

With a 'swapped' flag as I'd normally use it, both are fast when data is 
already sorted. Without that flag, it's only suitable for very small 
data sets.

(my tests seems to show bubble is twice as fast as insertion, taking 0.2 
seconds interpreted even for 1M sorted elements, which is extraordinary 
enough I'd have to double-check. But a quick look suggests that my 
insertion sort will always move each element even if it's to the same 
place.)

> 
> I think your criteria for code elegance are jumbled.

I like to use simple, linear algorithms where possible. All my language 
projects have very good throughput (100s of thousands to even millions 
of lines per second), yet the most sophisticated data structure is a 
single hash-table, using my own hash-function. Everything else is done 
with linear traversal of linked lists or arrays.)

[toc] | [prev] | [next] | [standalone]

#147317

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Date	2019-10-28 23:59 +0000
Message-ID	<87y2x4pgk0.fsf@bsb.me.uk>
In reply to	#147314

Bart <bc@freeuk.com> writes:

> On 28/10/2019 21:08, Ben Bacarisse wrote:
>> Bart <bc@freeuk.com> writes:
>>
>>> I just have a soft soft for bubble sort; the way it works, the way the
>>> action is always localised, is aesthetically pleasing.
>>
>> I will re-iterate that what you call bubble sort is this:
>>
>>    for (int i = 0; i < n; i++)
>
> I think n-1 will do here.

Yes, but I was transliterating the code you wrote in order to keep
things concrete.

>>       for (int j = 1; j < n; j++)
>>          if (a[j-1] > a[j])
>>             swap(&a[j-1], a&[j]);
>>
>> You praise the way the action is always localised but it is also
>> localised in this version of insertion sort:
>>
>>    for (int i = 1; i < n; i++)
>>       for (int j = i; j > 0 && a[j-1] > a[j]; j--)
>>          swap(&a[j-1], &a[j]);
>>
>> so you will, no doubt, praise that too, yes?
>
> Yes, but it seems insertion can be written in more diverse ways.

Sorry, but this is nonsense.  The two versions of insertion sort that
have come up here are essentially the same.  The one that picks up a[j]
and puts in in place at the end of the loop follows from expanding the
swap out into the usual t = a[j-1], a[j-1] = a[j], a[j] = t; pattern.
It replaces a sequence of consecutive swaps with a rotate.

The two versions of bubble sort doing the rounds in this thread are
radically different in the pattern of comparisons done, in the pattern of
element moved and in the code itself.

> I've already said bubble-sort is more consistent.
>
> The main deviation is whether to opt to finish early, which would be a
> good idea if data might already be nearly sorted.

That is a significant algorithmic change, unlike changing a series of
consecutive swaps with a shift of the elements.

You keep equivocating.  The "stop when sorted" bubble sort is not simple
and elegant, so you don't show that when simple and elegant are the
things you are championing.  But when it's pointed out that this comes
for free with all implementations of insertion sort, you accept that
this is the bubble sort one should use.

>> You like the way the first works, even with its frequent pointless tests
>> when the data is already sorted (or almost sorted), but /I/ like the
>> fact that the second detects this condition and back out early with no
>> extra code or flags (unlike the real bubble sort that needs both).
>> Don't you like that about how insertion sort works?
>>
>> All that's left is aesthetics, and in that department the second
>> algorithm wins hands down for me, but that's harder to argue.
>>
>>> It just has a slightly lower threshold at which it stops being viable
>>> than insertion sort,
>>
>> You may remember Malcolm's original remark about frequently having to
>> sort short collections of almost-sorted data.  Even a small extra cost
>> might be significant when the operation is done often enough.  The
>> algorithm you are championing does n*(n-1) compares /every time/, even
>> when the data are sorted.  The second code does n-1 compares on sorted
>> data.  So that's only 80 more compares on a 10-elements array, or 361
>> more if there are 20 elements, but why pay that price when the second
>> code is so simple and so elegant?
>
> With a 'swapped' flag as I'd normally use it, both are fast when data
> is already sorted. Without that flag, it's only suitable for very
> small data sets.

But that was not the algorithm you've been championing!  Please show
this better bubble sort so we can all see what you think is
aesthetically pleasing about that code.  It will help to clarify what
rage of alternatives you accept whilst still keeping bubble sort "more
consistent" than insertion sort.

> (my tests seems to show bubble is twice as fast as insertion, taking
> 0.2 seconds interpreted even for 1M sorted elements, which is
> extraordinary enough I'd have to double-check. But a quick look
> suggests that my insertion sort will always move each element even if
> it's to the same place.)

One of the few good things about bubble sort (the real one, not the
algorithm you seem to have been talking about up until now) is that the
loop logic is usually very fast when the data are sorted, but the best
algorithm for such data is not bubble sort, it's no sort.  Even less
than one element out of place will usually tip the balance (i.e. one
element out of place every now and then).

But down among these very fast cases exactly how the loops are coded, as
well as what the optimiser can get hold of, becomes more and more
significant.  It gets to be less and less about algorithms.

>> I think your criteria for code elegance are jumbled.
>
> I like to use simple, linear algorithms where possible. All my
> language projects have very good throughput (100s of thousands to even
> millions of lines per second), yet the most sophisticated data
> structure is a single hash-table, using my own
> hash-function. Everything else is done with linear traversal of linked
> lists or arrays.)

We were talking about sorting.  I've no way of assessing your criteria
for elegance in any other cases.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#147318

From	Bart <bc@freeuk.com>
Date	2019-10-29 00:53 +0000
Message-ID	<B4MtF.50754$m0L.24043@fx15.am4>
In reply to	#147317

On 28/10/2019 23:59, Ben Bacarisse wrote:
> Bart <bc@freeuk.com> writes:

>> With a 'swapped' flag as I'd normally use it, both are fast when data
>> is already sorted. Without that flag, it's only suitable for very
>> small data sets.
> 
> But that was not the algorithm you've been championing!

I showed the one without the early stop because you complained that 
bubble sort needed the early stop flag. It can be done without, but 
using one will add 1-2 lines (depending on how you count significant lines).

   Please show
> this better bubble sort so we can all see what you think is
> aesthetically pleasing about that code.  It will help to clarify what
> rage of alternatives you accept whilst still keeping bubble sort "more
> consistent" than insertion sort.

Here are the 3 sorts we've been discussing (in my script language but it 
will do the job of pseudo-code, however bsort/isort assume 1-based 
lists). I've removed blank lines to make them easier to compare. I 
understand the insertion sort could be written more succinctly but this 
is what I've been using:

   proc bubble_sort(a)=
       repeat
           sorted:=1
           for i to a.len-1 when a[i]>a[i+1] do
               swap(a[i],a[i+1])
               sorted:=0
           od
       until sorted
   end

   proc insertion_sort(a)=
       for i:=2 to a.len do
           value:=a[i]
           holepos:=i
           while holepos>1 and a[holepos-1]>value do
               a[holepos]:=a[holepos-1]
               --holepos
           od
           a[holepos]:=value
       od
   end

   proc quick_sort(a)=
       i:=ll:=a.lwb
       j:=rr:=a.upb
       pivot:=a[(ll+rr)%2]
       repeat
           while pivot>a[i] and i<rr do ++i od
           while pivot<a[j] and j>ll do --j od
           if i<=j then
              swap(a[i++],a[j--])
           fi
       until i>j
       if ll<j then quick_sort(a[ll..j]) fi
       if i<rr then quick_sort(a[i..rr]) fi
   end

[toc] | [prev] | [next] | [standalone]

#147319

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Date	2019-10-29 01:09 +0000
Message-ID	<87sgncpdc2.fsf@bsb.me.uk>
In reply to	#147318

Bart <bc@freeuk.com> writes:

> On 28/10/2019 23:59, Ben Bacarisse wrote:
>> Bart <bc@freeuk.com> writes:
>
>>> With a 'swapped' flag as I'd normally use it, both are fast when data
>>> is already sorted. Without that flag, it's only suitable for very
>>> small data sets.
>>
>> But that was not the algorithm you've been championing!
>
> I showed the one without the early stop because you complained that
> bubble sort needed the early stop flag.

No I didn't.

>>   Please show
>> this better bubble sort so we can all see what you think is
>> aesthetically pleasing about that code.  It will help to clarify what
>> rage of alternatives you accept whilst still keeping bubble sort "more
>> consistent" than insertion sort.
>
> Here are the 3 sorts we've been discussing

No, these are not the sorts we have been discussing.  For most of the
thread I've been discussion a sort you posted about that is not bubble
sort and is not one of the three you've shown here.  And the insertion
sort that I have been talking about is not one of them either.

> (in my script language but it will do the job of pseudo-code, however
> bsort/isort assume 1-based lists).

This is comp.lang.c.  I've been talking about C code.  I'm not going to
post sorting code in a language unknown to me in any group, and
certainly not here.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#147320

From	Bart <bc@freeuk.com>
Date	2019-10-29 01:32 +0000
Message-ID	<IEMtF.2768$vc.1601@fx20.am4>
In reply to	#147319

On 29/10/2019 01:09, Ben Bacarisse wrote:
> Bart <bc@freeuk.com> writes:
> 
>> On 28/10/2019 23:59, Ben Bacarisse wrote:
>>> Bart <bc@freeuk.com> writes:
>>
>>>> With a 'swapped' flag as I'd normally use it, both are fast when data
>>>> is already sorted. Without that flag, it's only suitable for very
>>>> small data sets.
>>>
>>> But that was not the algorithm you've been championing!
>>
>> I showed the one without the early stop because you complained that
>> bubble sort needed the early stop flag.
> 
> No I didn't.
> 
>>>    Please show
>>> this better bubble sort so we can all see what you think is
>>> aesthetically pleasing about that code.  It will help to clarify what
>>> rage of alternatives you accept whilst still keeping bubble sort "more
>>> consistent" than insertion sort.
>>
>> Here are the 3 sorts we've been discussing
> 
> No, these are not the sorts we have been discussing.  For most of the
> thread I've been discussion a sort you posted about that is not bubble
> sort and is not one of the three you've shown here.  And the insertion
> sort that I have been talking about is not one of them either.

You're being hard.

If that B-sort isn't bubble-sort (whatever that officially needs to 
comprise) and that I-sort isn't insertion-sort, then I must have 
invented my very own sort algorithms!

(Actually the I-sort was taken from a source on-line that called it 
'insertion sort':
https://www.tutorialspoint.com/data_structures_algorithms/insertion_sort_algorithm.htm.

While their version of 'bubble sort' isn't that different from mine.)

  language but it will do the job of pseudo-code, however
>> bsort/isort assume 1-based lists).
> 
> This is comp.lang.c.  I've been talking about C code.  I'm not going to
> post sorting code in a language unknown to me in any group, and
> certainly not here.
> 

You're being hard.

Sorting is about algorithms, and algorithms can be expressed in pseudo-code.

People (not you obviously) do play around with pseudo-code or with a 
more forgiving language before committing to more concrete code in a 
language like C. Both those links above show pseudo-code.

If you really need to see C code, I posted runnable versions of my 
insertion and quick sort earlier on Monday. While what /I/ call bubble 
sort (obviously not what you consider bubble sort) can be illustrated 
with this fragment:

     do {
         swapped=0;
         for (i=1; i<n; ++i) {
             if (data[i]>data[i+1]) {
                 swapped=1;
                 t=data[i];
                 data[i]=data[i+1];
                 data[i+1]=t;
             }
         }
     } while (swapped);

[toc] | [prev] | [next] | [standalone]

#147321

From	DFS <nospam@dfs.com>
Date	2019-10-28 22:44 -0400
Message-ID	<zJNtF.145514$rR2.139296@fx23.iad>
In reply to	#147320

On 10/28/2019 9:32 PM, Bart wrote:



> (Actually the I-sort was taken from a source on-line that called it 
> 'insertion sort':
> https://www.tutorialspoint.com/data_structures_algorithms/insertion_sort_algorithm.htm. 

I like this visualization of insertion sort:
https://www.geeksforgeeks.org/insertion-sort/

[toc] | [prev] | [next] | [standalone]

Page 4 of 6 — ← Prev page 1 2 3 [4] 5 6 Next page →

csiph-web

Challenge for Feeb: dealing with large numbers in C

Contents

#147301

#147303

#147304

#147305

#147307

#147310

#147311

#147312

#147315

#147323

#147327

#147308

#147309

#147313

#147314

#147317

#147318

#147319

#147320

#147321