Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

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

Challenge for Feeb: dealing with large numbers in C

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

Contents

  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 3 of 6 — ← Prev page 1 2 [3] 4 5 6  Next page →

#147219

On 10/24/2019 3:36 PM, Ben Bacarisse wrote:
> Bart <bc@freeuk.com> writes:
> 
>> On 24/10/2019 01:38, Ben Bacarisse wrote:
>>> DFS <nospam@dfs.com> writes:
>>>
>>>> You don't have to make a separate list V[] to store the sorted letters
>>>> (though using such a list would be faster).
>>>>
>>>> This code makes one pass thru the dictionary, comparing the sorted
>>>> letters of the search word against the sorted letters of each word in
>>>> the dictionary.
>>>
>>> Surely it's faster to count letters?  On my machine a simple letter
>>> counting version takes about 1/4 of the time your program takes.
>>
>> Can you post code for a letter-counting version (that works off an
>> external word list), or have you posted one already?
> 
> I didn't want to because I had not fixed any of the issues with the
> original.  I just hacked a letter count into the code.  For what it's
> worth, I've appended it as the end.
> 
>> With the OP's sorting version:
>>
>> (1) The words are read via fgets with line-endings attached, and need
>> to be trimmed
> 
> I kept that.  I wanted a direct comparison.  Profiling on Linux showed
> that most of the time was spent in wsort so there was clearly room for
> improvement.
> 
>> (2) Bubble sort is applied to every word in the list
> 
> I don't call that bubble sort, but let's not have that discussion again!

ha!

Some people really hate it: "some researchers such as Owen Astrachan 
have gone to great lengths to disparage bubble sort and its continued 
popularity in computer science education, recommending that it no longer 
even be taught."

https://users.cs.duke.edu/~ola/papers/bubble.pdf



>> (I don't know if your '1/4' of the time compares times on your machine
>> with the OP's reported time, but they appear to be using Tiny C.)
> 
> It compared the original (compiled with gcc -O2) with the counting
> version (obtained simply by adding -DCOUNTING), both running on the same
> Linux laptop.  The numbers a so small that I doubt the ratio is really
> accurate (roughly 0.132 vs 0.035 seconds when I tried today).


$ tcc -o ben.exe -DCOUNTING ana_Ben_counts.c
$ ptime ben words_alpha.txt players
7 anagram(s) found in 370099 words
Execution time: 0.215 s


my code (no letter counting, uses strlen()):
$ ptime alpha words_alpha.txt players
7 anagram(s) found in 370099 words
Execution time: 0.192 s


> Code:
> 
> #include <stdlib.h>
> #include <stdio.h>
> #include <string.h>
> 
> #ifdef COUNTING
> #define N_LETTERS 26
> 
> void wcount(const char *s, unsigned char *c)
> {
>       memset(c, 0, N_LETTERS);
>       while (*s) c[*s++ - 'a']++;
> }
> int eq_count(const char *s, const unsigned char *c)
> {
>       unsigned char sc[N_LETTERS];
>       wcount(s, sc);
>       return memcmp(c, sc, N_LETTERS) == 0;
> }
> 
> #else
> 
> //bubble sort word in alpha order
> char *wsort(char *s, int len)
> {
>    char t;
>    for(int i=0;i<len-1;i++) {
>       for(int j=i+1;j<len;j++) {
>          if(s[i]>s[j]) {
>             t=s[i];
>             s[i]=s[j];
>             s[j]=t;
>          }
>       }
>    }
> }
> 
> #endif
> 
> //trim trailing spaces
> void rtrim(char *str, int len)
> {
>   while(len>0 && isspace(str[len-1])){len--;}
>   str[len] = '\0';
> }
> 
> //read file, find anagrams
> int main(int argc, char *argv[])
> {
>      // w   = word in dictionary
>      // ws  = alpha sort of the word
>      // s   = search word you want anagrams for
>      // ss  = alpha sort of the search word
>      // mws = max word size
>      // wc  = word count in dict
> 
>      int i=0,wc=0,mws=33;
>      char w[mws], ws[mws], ss[mws];
>      char *s = argv[2];
> 
> #ifdef COUNTING
>      unsigned char ac[N_LETTERS];
>      wcount(s, ac);
> #else
>      strcpy(ss,s);
>      wsort(ss,strlen(ss));
> #endif
> 
>      FILE *fw = fopen(argv[1],"r");
>      while(fgets(w,sizeof(w),fw)!=NULL) {
>          rtrim(w,strlen(w));
> #ifdef COUNTING
>          if (eq_count(w, ac)) {
> #else
>          strcpy(ws,w);
>          wsort(ws,strlen(ws));
>          if(strcmp(ws,ss)==0) {
> #endif
>            if(strcmp(w,s)!=0) {
>              printf("%s\n",w);
>              i++;
>            }
>          }
>          wc++;
>      }
> 
>      printf("%d anagram(s) found in %d words\n",i,wc);
>      fclose(fw);
>      exit(0);
> }
> 

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

#147222

DFS <nospam@dfs.com> writes:

> On 10/24/2019 3:36 PM, Ben Bacarisse wrote:
>> Bart <bc@freeuk.com> writes:
>>
>>> On 24/10/2019 01:38, Ben Bacarisse wrote:
>>>> DFS <nospam@dfs.com> writes:
>>>>
>>>>> You don't have to make a separate list V[] to store the sorted letters
>>>>> (though using such a list would be faster).
>>>>>
>>>>> This code makes one pass thru the dictionary, comparing the sorted
>>>>> letters of the search word against the sorted letters of each word in
>>>>> the dictionary.
>>>>
>>>> Surely it's faster to count letters?  On my machine a simple letter
>>>> counting version takes about 1/4 of the time your program takes.
>>>
>>> Can you post code for a letter-counting version (that works off an
>>> external word list), or have you posted one already?
>>
>> I didn't want to because I had not fixed any of the issues with the
>> original.  I just hacked a letter count into the code.  For what it's
>> worth, I've appended it as the end.
>>
>>> With the OP's sorting version:
>>>
>>> (1) The words are read via fgets with line-endings attached, and need
>>> to be trimmed
>>
>> I kept that.  I wanted a direct comparison.  Profiling on Linux showed
>> that most of the time was spent in wsort so there was clearly room for
>> improvement.
>>
>>> (2) Bubble sort is applied to every word in the list
>>
>> I don't call that bubble sort, but let's not have that discussion again!
>
> ha!
>
> Some people really hate it: "some researchers such as Owen Astrachan
> have gone to great lengths to disparage bubble sort and its continued
> popularity in computer science education, recommending that it no
> longer even be taught."

We seem always to be talking at cross purposes.  My point is simply that
what you wrote is not bubble sort, so whether anyone hates it or not is
beside the point.

> https://users.cs.duke.edu/~ola/papers/bubble.pdf

As this paper shows, bubble sort only ever compares (and therefore
swaps) adjacent elements.  Personally, I think bubble sort should also
stop when no swaps are done in a pass, but obviously, not everyone
agrees with that.

>>> (I don't know if your '1/4' of the time compares times on your machine
>>> with the OP's reported time, but they appear to be using Tiny C.)
>>
>> It compared the original (compiled with gcc -O2) with the counting
>> version (obtained simply by adding -DCOUNTING), both running on the same
>> Linux laptop.  The numbers a so small that I doubt the ratio is really
>> accurate (roughly 0.132 vs 0.035 seconds when I tried today).
>
>
> $ tcc -o ben.exe -DCOUNTING ana_Ben_counts.c
> $ ptime ben words_alpha.txt players
> 7 anagram(s) found in 370099 words
> Execution time: 0.215 s
>
> my code (no letter counting, uses strlen()):
> $ ptime alpha words_alpha.txt players
> 7 anagram(s) found in 370099 words
> Execution time: 0.192 s

I'm not sure what your point is.  In case it was not obvious, /my/ point
was that counting letter frequencies is faster than sorting letters.  If
you only sort letters on words that match in length then the results
will depend on all sorts of other factors, including the data.

But I am surprised your times are so high.  Maybe your tests are being
swamped by IO processing, but if they are not, you can get a further
speed-up (though obviously a much less dramatic one) by using letter
counting in your second program as well.

-- 
Ben.

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

#147241

On Friday, 25 October 2019 00:01:03 UTC+1, DFS  wrote:

> Some people really hate it: "some researchers such as Owen Astrachan 
> have gone to great lengths to disparage bubble sort and its continued 
> popularity in computer science education, recommending that it no longer 
> even be taught."
> 
> https://users.cs.duke.edu/~ola/papers/bubble.pdf
> 
The first algorithm taught should be one that can be improved.

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

#147245

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

> On Friday, 25 October 2019 00:01:03 UTC+1, DFS  wrote:
>
>> Some people really hate it: "some researchers such as Owen Astrachan 
>> have gone to great lengths to disparage bubble sort and its continued 
>> popularity in computer science education, recommending that it no longer 
>> even be taught."
>> 
>> https://users.cs.duke.edu/~ola/papers/bubble.pdf
>> 
> The first algorithm taught should be one that can be improved.

But does it have to be the worst?

-- 
Ben.

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

#147250

On 26/10/2019 17:21, Ben Bacarisse wrote:
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
> 
>> On Friday, 25 October 2019 00:01:03 UTC+1, DFS  wrote:
>>
>>> Some people really hate it: "some researchers such as Owen Astrachan
>>> have gone to great lengths to disparage bubble sort and its continued
>>> popularity in computer science education, recommending that it no longer
>>> even be taught."
>>>
>>> https://users.cs.duke.edu/~ola/papers/bubble.pdf
>>>
>> The first algorithm taught should be one that can be improved.
> 
> But does it have to be the worst?

Worst performance? It doesn't matter. Bubble sort is conceptually 
simple. The fact that it has O(n**2) performance can itself be educational.

And for small data sets, it will likely be fast enough for practical 
purposes.

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

#147270

Bart <bc@freeuk.com> writes:

> On 26/10/2019 17:21, Ben Bacarisse wrote:
>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>
>>> On Friday, 25 October 2019 00:01:03 UTC+1, DFS  wrote:
>>>
>>>> Some people really hate it: "some researchers such as Owen Astrachan
>>>> have gone to great lengths to disparage bubble sort and its continued
>>>> popularity in computer science education, recommending that it no longer
>>>> even be taught."
>>>>
>>>> https://users.cs.duke.edu/~ola/papers/bubble.pdf
>>>>
>>> The first algorithm taught should be one that can be improved.
>>
>> But does it have to be the worst?
>
> Worst performance? It doesn't matter. Bubble sort is conceptually
> simple. The fact that it has O(n**2) performance can itself be
> educational.
>
> And for small data sets, it will likely be fast enough for practical
> purposes.

Insertion sort is conceptually simple. The fact that it has o(n**2)
performance can itself be educational.

And for small data sets, it will likely be fast enough for practical
purposes, and won't be worse than other o(n**2) algorithms.

-- 
Ben.

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

#147272

On 26/10/2019 23:24, Ben Bacarisse wrote:
> Bart <bc@freeuk.com> writes:
> 
>> On 26/10/2019 17:21, Ben Bacarisse wrote:
>>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>>
>>>> On Friday, 25 October 2019 00:01:03 UTC+1, DFS  wrote:
>>>>
>>>>> Some people really hate it: "some researchers such as Owen Astrachan
>>>>> have gone to great lengths to disparage bubble sort and its continued
>>>>> popularity in computer science education, recommending that it no longer
>>>>> even be taught."
>>>>>
>>>>> https://users.cs.duke.edu/~ola/papers/bubble.pdf
>>>>>
>>>> The first algorithm taught should be one that can be improved.
>>>
>>> But does it have to be the worst?
>>
>> Worst performance? It doesn't matter. Bubble sort is conceptually
>> simple. The fact that it has O(n**2) performance can itself be
>> educational.
>>
>> And for small data sets, it will likely be fast enough for practical
>> purposes.
> 
> Insertion sort is conceptually simple.

Bubble sort is simpler. You only ever compare or swap adjacent elements.

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

#147274

Bart <bc@freeuk.com> writes:

> On 26/10/2019 23:24, Ben Bacarisse wrote:
>> Bart <bc@freeuk.com> writes:
>>
>>> On 26/10/2019 17:21, Ben Bacarisse wrote:
>>>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>>>
>>>>> On Friday, 25 October 2019 00:01:03 UTC+1, DFS  wrote:
>>>>>
>>>>>> Some people really hate it: "some researchers such as Owen Astrachan
>>>>>> have gone to great lengths to disparage bubble sort and its continued
>>>>>> popularity in computer science education, recommending that it no longer
>>>>>> even be taught."
>>>>>>
>>>>>> https://users.cs.duke.edu/~ola/papers/bubble.pdf
>>>>>>
>>>>> The first algorithm taught should be one that can be improved.
>>>>
>>>> But does it have to be the worst?
>>>
>>> Worst performance? It doesn't matter. Bubble sort is conceptually
>>> simple. The fact that it has O(n**2) performance can itself be
>>> educational.
>>>
>>> And for small data sets, it will likely be fast enough for practical
>>> purposes.
>>
>> Insertion sort is conceptually simple.
>
> Bubble sort is simpler. You only ever compare or swap adjacent
> elements.

Insertion sort is simpler.  You only ever compare or swap adjacent
elements and there is no "out of order" flag.  (I'm assuming we are both
allowed pick whatever version of both algorithms allows us to score
maximum points in this silly exchange.  If not, do say what the rules
are.)

-- 
Ben

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

#147284

On 27/10/2019 01:58, Ben Bacarisse wrote:
> Bart <bc@freeuk.com> writes:

>> Bubble sort is simpler. You only ever compare or swap adjacent
>> elements.
> 
> Insertion sort is simpler.  You only ever compare or swap adjacent
> elements and there is no "out of order" flag. 

See below where there is no flag.

> (I'm assuming we are both
> allowed pick whatever version

You're the one that's picking. I had to go and look up insertion sort, 
each reference seemed to have a different explanation and different 
algorithm. The algorithm for bubble sort is more consistent.

  of both algorithms allows us to score
> maximum points in this silly exchange.  If not, do say what the rules
> are.)

So what is your point, that insertion sort is equally inefficient, but 
that you prefer it over bubble sort?

I prefer the latter since I know how to write it! (Actually I did so in 
a job interview in 1978, where I was asked to write some Fortran code to 
sort an array. It must have been OK since I was offered the job.)

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

   proc bsort2(a)=
       to a.len do
           for i to a.len-1 when a[i] > a[i+1] do
               swap(a[i], a[i+1])
           od
       od
   end

(In-place bubble-sort on 1-based list of anything where ">" is defined.)

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

#147302

Bart <bc@freeuk.com> writes:

> On 27/10/2019 01:58, Ben Bacarisse wrote:
>> Bart <bc@freeuk.com> writes:
>
>>> Bubble sort is simpler. You only ever compare or swap adjacent
>>> elements.
>>
>> Insertion sort is simpler.  You only ever compare or swap adjacent
>> elements and there is no "out of order" flag. 
>
> See below where there is no flag.

That's not bubble sort according to Knuth and many others, but the name
is not the point here.

>> (I'm assuming we are both
>> allowed pick whatever version
>
> You're the one that's picking.

Yes, as are you.  You picked an algorithm that many people would not
even call bubble sort in order to make the claim that it's simple.

> So what is your point, that insertion sort is equally inefficient, but
> that you prefer it over bubble sort?

No, my point is that it is more efficient and no harder to write.  It's
way more efficient than the algorithm you are calling bubble sort, and
it's simpler (as well as more efficient) than the algorithm that Knuth
(and many others) call bubble sort.

> I prefer the latter since I know how to write it!

I don't see how what you know is relevant to what should be taught.  If
you are making a stronger claim -- that, based on your personal
experience, insertion sort is too complex to remember and thus is never
available "off the top of one's head" -- then I think that just reflects
what you've previously learned.

> (Actually I did so in a job interview in 1978, where I was asked to
> write some Fortran code to sort an array. It must have been OK since I
> was offered the job.)

What can anyone tell from this anecdote?  Maybe the interviewer shared
some of the common misconceptions about bubble sort.  Maybe they did not
care about the algorithm at all.  Maybe they hated your choice of
algorithm but everything else was good?  It's not a helpful story.

>   proc bsort2(a)=
>       to a.len do
>           for i to a.len-1 when a[i] > a[i+1] do
>               swap(a[i], a[i+1])
>           od
>       od
>   end
>

So, this (in C) is the algorithm you are defending:

  void bart_sort(int n, T a[])
  {
     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]);
  }

(I've made the inner loop run from 1 and used j-1 rather than j+1
because that feels a bit more C-like, but such details are beside the
point here.)

Many authors would not call that bubble sort.  Bubble sort is usually
seen as stopping early when the array is sorted:

  void bubble_sort(int n, T a[])
  {
     bool swapped;
     do {
        swapped = false;
        for (int j = 1; j < n; j++)
           if (a[j-1] > a[j]) {
              swap(&a[j-1], &a[j]);
              swapped = true;
           }
     } while (swapped);
  }

what I am saying is that everyone who might need it should just remember

  void insertion_sort(int n, T a[])
  {
     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]);
  }

because it's simpler and more efficient.  Obviously there are even more
efficient ways to write this -- maybe even using a block move -- but,
again, that's not really the point here.

(Code typed in late at night and not shown to a compiler let alone a
test harness so take it with a pinch of salt.)

-- 
Ben.

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

#147263

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>
>> On Friday, 25 October 2019 00:01:03 UTC+1, DFS  wrote:
>>
>>> Some people really hate it: "some researchers such as Owen Astrachan 
>>> have gone to great lengths to disparage bubble sort and its continued 
>>> popularity in computer science education, recommending that it no longer 
>>> even be taught."
>>> 
>>> https://users.cs.duke.edu/~ola/papers/bubble.pdf
>>> 
>> The first algorithm taught should be one that can be improved.
>
> But does it have to be the worst?

You lack imagination.  My favorite bad sorting algorithm is permutation
sort, which generates all permutations on the input data and picks the
one that's sorted.  This is, of course, what one gets if one writes a
naive sort in Prolog.

Another really bad one is random sort.  This one generates random
permutations of the input until it gets one that's sorted.  It's
expected time is as bad as permutation sort, but it has no bound on its
worst case performance.

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

#147264

Joe Pfeiffer <pfeiffer@cs.nmsu.edu> writes:
[...]
> You lack imagination.  My favorite bad sorting algorithm is permutation
> sort, which generates all permutations on the input data and picks the
> one that's sorted.  This is, of course, what one gets if one writes a
> naive sort in Prolog.

The optimized version of permutation sort allows you to stop searching
when you find the permutation that's sorted.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Will write code for food.
void Void(void) { Void(); } /* The recursive call of the void */

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

#147266

On 26/10/2019 21:29, Joe Pfeiffer wrote:
> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
> 
>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>
>>> On Friday, 25 October 2019 00:01:03 UTC+1, DFS  wrote:
>>>
>>>> Some people really hate it: "some researchers such as Owen Astrachan
>>>> have gone to great lengths to disparage bubble sort and its continued
>>>> popularity in computer science education, recommending that it no longer
>>>> even be taught."
>>>>
>>>> https://users.cs.duke.edu/~ola/papers/bubble.pdf
>>>>
>>> The first algorithm taught should be one that can be improved.
>>
>> But does it have to be the worst?
> 
> You lack imagination.  My favorite bad sorting algorithm is permutation
> sort, which generates all permutations on the input data and picks the
> one that's sorted.  This is, of course, what one gets if one writes a
> naive sort in Prolog.
> 
> Another really bad one is random sort.  This one generates random
> permutations of the input until it gets one that's sorted.  It's
> expected time is as bad as permutation sort, but it has no bound on its
> worst case performance.

I like algorithms that randomly arrive at solutions, even if they are 
not optimal. For sorting lists of random numbers, I got these results so 
far, by swapping random elements until the whole list was sorted:

2-element list took 0 swaps and 0 ticks
3-element list took 5 swaps and 0 ticks
4-element list took 26 swaps and 0 ticks
5-element list took 79 swaps and 0 ticks
6-element list took 349 swaps and 0 ticks
7-element list took 4383 swaps and 1 ticks
8-element list took 64075 swaps and 20 ticks
9-element list took 130790 swaps and 45 ticks
10-element list took 2711210 swaps and 880 ticks
11-element list took 27700684 swaps and 8967 ticks
12-element list took 125801829 swaps and 40752 ticks
13-element list took 2610718236 swaps and 845409 ticks

(Ticks are msec counts, for interpreted code.) There is a rough 
correlation between the number of swaps and N!, so perhaps not that 
different to a permutation sort, just less reliable.

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

#147268

Joe Pfeiffer <pfeiffer@cs.nmsu.edu> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>
>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>
>>> On Friday, 25 October 2019 00:01:03 UTC+1, DFS  wrote:
>>>
>>>> Some people really hate it: "some researchers such as Owen Astrachan 
>>>> have gone to great lengths to disparage bubble sort and its continued 
>>>> popularity in computer science education, recommending that it no longer 
>>>> even be taught."
>>>> 
>>>> https://users.cs.duke.edu/~ola/papers/bubble.pdf
>>>> 
>>> The first algorithm taught should be one that can be improved.
>>
>> But does it have to be the worst?
>
> You lack imagination.

No I don't!  I'm trying to make a point without being overly wordy.  I
know there are worse ways to sort, but bubble sort is the worst of the
simple ones that get frequently taught.  The problem is that students
remember it and use it.

> My favorite bad sorting algorithm is permutation
> sort, which generates all permutations on the input data and picks the
> one that's sorted.  This is, of course, what one gets if one writes a
> naive sort in Prolog.

Re Prolog, I disagree, but this is not the place to hash that out.
What's more you don't get this sort in C "by accident".

> Another really bad one is random sort.  This one generates random
> permutations of the input until it gets one that's sorted.  It's
> expected time is as bad as permutation sort, but it has no bound on its
> worst case performance.

How often have you seen this algorithm used where you know a better (and
shorter) one exists?  Whilst students might remember these humorous
awful algorithms, you don't keep seeing them in real code.  In that
sense they are not the worst ones to teach.

-- 
Ben.

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

#147280

On 26/10/2019 18:21, Ben Bacarisse wrote:
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
> 
>> On Friday, 25 October 2019 00:01:03 UTC+1, DFS  wrote:
>>
>>> Some people really hate it: "some researchers such as Owen Astrachan
>>> have gone to great lengths to disparage bubble sort and its continued
>>> popularity in computer science education, recommending that it no longer
>>> even be taught."
>>>
>>> https://users.cs.duke.edu/~ola/papers/bubble.pdf
>>>
>> The first algorithm taught should be one that can be improved.
> 
> But does it have to be the worst?
> 

Surely you can think of far worse sort algorithms than Bubblesort (even 
a poorly implemented Bubblesort)?  What about "Bogosort" (with many 
alternative names), where you randomly re-order the data and check if it 
is sorted, repeating until you are done?

Bubblesort is very simple to understand and thus a good starting choice. 
  It is not efficient at O(n²), but it is not too bad and does not 
suffer from complications like wildly different average and worst-case 
efficiencies (such as a straightforward Quicksort does).  And most of 
the next-level complexity sorts are O(n.log n) complexity - it is easy 
for the learner to see how Bubblesort can be usefully replaced with 
Merge sort, Insertion sort or Heap sort, but harder to understand when 
you might replace one of these three with a different one.

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

#147293

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

> On 26/10/2019 18:21, Ben Bacarisse wrote:
>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>
>>> On Friday, 25 October 2019 00:01:03 UTC+1, DFS  wrote:
>>>
>>>> Some people really hate it: "some researchers such as Owen Astrachan
>>>> have gone to great lengths to disparage bubble sort and its continued
>>>> popularity in computer science education, recommending that it no longer
>>>> even be taught."
>>>>
>>>> https://users.cs.duke.edu/~ola/papers/bubble.pdf
>>>>
>>> The first algorithm taught should be one that can be improved.
>>
>> But does it have to be the worst?
>>
>
> Surely you can think of far worse sort algorithms than Bubblesort
> (even a poorly implemented Bubblesort)?

Of course.  I am sure you know what I meant.

> What about "Bogosort" (with
> many alternative names), where you randomly re-order the data and
> check if it is sorted, repeating until you are done?
>
> Bubblesort is very simple to understand and thus a good starting
> choice.

Insertion sort is very simple to understand and thus a good starting point.

> It is not efficient at O(n²), but it is not too bad and does not
> suffer from complications like wildly different average and worst-case
> efficiencies (such as a straightforward Quicksort does).

All these apply to insertion sort.

> And most of the next-level complexity sorts are O(n.log n) complexity
> - it is easy for the learner to see how Bubblesort can be usefully
> replaced with Merge sort, Insertion sort or Heap sort, but harder to
> understand when you might replace one of these three with a different
> one.

Eh?  A learner see how insertion sort can be usefully replaced with
merge sort, heap sort, shell sort, quick sort, etc.  Is bubble sort's
advantage that it is bad enough to replace with another quadratic
algorithm?  That's an odd reason to teach it.

-- 
Ben.

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

#147297

On 27/10/2019 19:20, Ben Bacarisse wrote:
> David Brown <david.brown@hesbynett.no> writes:
> 
>> On 26/10/2019 18:21, Ben Bacarisse wrote:
>>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>>
>>>> On Friday, 25 October 2019 00:01:03 UTC+1, DFS  wrote:
>>>>
>>>>> Some people really hate it: "some researchers such as Owen Astrachan
>>>>> have gone to great lengths to disparage bubble sort and its continued
>>>>> popularity in computer science education, recommending that it no longer
>>>>> even be taught."
>>>>>
>>>>> https://users.cs.duke.edu/~ola/papers/bubble.pdf
>>>>>
>>>> The first algorithm taught should be one that can be improved.
>>>
>>> But does it have to be the worst?
>>>
>>
>> Surely you can think of far worse sort algorithms than Bubblesort
>> (even a poorly implemented Bubblesort)?
> 
> Of course.  I am sure you know what I meant.
> 
>> What about "Bogosort" (with
>> many alternative names), where you randomly re-order the data and
>> check if it is sorted, repeating until you are done?
>>
>> Bubblesort is very simple to understand and thus a good starting
>> choice.
> 
> Insertion sort is very simple to understand and thus a good starting point.
> 

Yes, insertion sort would make a perfectly good alternative to 
bubblesort.  That does not mean bubblesort is a bad choice for a 
starting point.

>> It is not efficient at O(n²), but it is not too bad and does not
>> suffer from complications like wildly different average and worst-case
>> efficiencies (such as a straightforward Quicksort does).
> 
> All these apply to insertion sort.
> 
>> And most of the next-level complexity sorts are O(n.log n) complexity
>> - it is easy for the learner to see how Bubblesort can be usefully
>> replaced with Merge sort, Insertion sort or Heap sort, but harder to
>> understand when you might replace one of these three with a different
>> one.
> 
> Eh?  A learner see how insertion sort can be usefully replaced with
> merge sort, heap sort, shell sort, quick sort, etc.  Is bubble sort's
> advantage that it is bad enough to replace with another quadratic
> algorithm?  That's an odd reason to teach it.
> 

I didn't mean to have insertion sort on that list with merge sort and 
heap sort.  The point was that it is easy to see the advantages in 
moving from an O(n²) algorithm to an O(n.log n) algorithm - it is harder 
to see the advantages of different algorithms with the same average 
complexity.

I can agree that insertion sort can be a good choice of first sorting 
algorithm when learning about these things.  I just don't agree that 
there is any problem with using bubblesort for that purpose.

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

#147299

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

<cut>
> Yes, insertion sort would make a perfectly good alternative to
> bubblesort.  That does not mean bubblesort is a bad choice for a
> starting point.

It's just a waste of time as you can't avoid teaching insertion sort.
It's an extra, and it has produced an odd effect: almost everyone can
remember only one simple sort, and it's the worst of the simple sorts.
Even if it's only worse by a tiny margin, it's still worse and, to me, a
pointless thing to spend time on.

<cut>
> ...  The point was that it is easy to see the advantages in
> moving from an O(n²) algorithm to an O(n.log n) algorithm - it is
> harder to see the advantages of different algorithms with the same
> average complexity.

I agree.  That's probably one reason why so many people reach for such
an inefficient quadratic sort.

> I can agree that insertion sort can be a good choice of first sorting
> algorithm when learning about these things.  I just don't agree that
> there is any problem with using bubblesort for that purpose.

There are simple swapping versions of insertion sort that are either
simpler than bubble sort (if you take the usual definitions of bubble
sort) or just as simple (if you take the broad definition that seems to
be in vogue round here).  Both are better than bubble sort in terms
of array accesses and comparisons, in some cases, dramatically so.
There's simply no up-side.

The only practical problem with teaching it is the waste of time.  Even
if you can argue that it's only trivially worse than insertion sort, why
bother?

-- 
Ben.

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

#147298

On Sunday, 27 October 2019 18:20:20 UTC, Ben Bacarisse  wrote:
>
> Eh?  A learner see how insertion sort can be usefully replaced with
> merge sort, heap sort, shell sort, quick sort, etc.  Is bubble sort's
> advantage that it is bad enough to replace with another quadratic
> algorithm?  That's an odd reason to teach it.
> 
Usually bubble sort will be the first algorithm taught (other than
things like the pencil and paper method for long multiplication,
which aren't understood at the time to be algorithms).

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.

Third lesson is quicksort, and the concept of big O notation for
algorithms. 

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

#147300

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

> On Sunday, 27 October 2019 18:20:20 UTC, Ben Bacarisse  wrote:
>>
>> Eh?  A learner see how insertion sort can be usefully replaced with
>> merge sort, heap sort, shell sort, quick sort, etc.  Is bubble sort's
>> advantage that it is bad enough to replace with another quadratic
>> algorithm?  That's an odd reason to teach it.
>> 
> Usually bubble sort will be the first algorithm taught (other than
> things like the pencil and paper method for long multiplication,
> which aren't understood at the time to be algorithms).

Most such courses include data structures, so many algorithms may well
have been covered by the time in-place array sorting is discussed.
Anyway, the question is why bother with bubble sort when the time comes?

> 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.

> Third lesson is quicksort, and the concept of big O notation for
> algorithms.

I would have already covered big O.  Sorting algorithms have actual,
average and worst-case complexities so it's better, in my opinion, to
have big O already reasonably well understood by having used it for
simpler algorithms.

-- 
Ben.

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

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

Back to top | Article view | comp.lang.c

csiph-web