Re: C++ threshold for "stupid" sorting algorithms (O(n^2))

From	Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups	comp.lang.c++
Subject	Re: C++ threshold for "stupid" sorting algorithms (O(n^2))
Date	2020-01-21 03:11 -0800
Organization	A noiseless patient Spider
Message-ID	<86iml5jc79.fsf@linuxsc.com> (permalink)
References	<qui2k6$rst$1@dont-email.me> <ukdp0ftld5mrph4p9q1sht942f4vvedak8@4ax.com> <86k15z3rm7.fsf@linuxsc.com> <fauh1ftsjuopokhmi3287165drd5ue2ku3@4ax.com>

Show all headers | View raw

Robert Wessel <robertwessel2@yahoo.com> writes:

> On Fri, 10 Jan 2020 13:53:52 -0800, Tim Rentsch
> <tr.17687@z991.linuxsc.com> wrote:
>
>> Robert Wessel <robertwessel2@yahoo.com> writes:
>>
>>> Generally the O(n**2) sorts are considered usable up a few tens of
>>> items.  And use insertion sort, not bubble sort (simpler algorithm,
>>> twice as fast on average).
>>
>> The simplest bubble sort is simpler than the simplest insertion
>> sort.
>>
>> The most complete bubble sort is simpler than the most complete
>> insertion sort.
>>
>> It is only if we compare a somewhat less complete rendition of
>> insertion sort to a somewhat more complete rendition of bubble
>> sort that "insertion sort" may be called simpler.
>>
>> I agree that insertion sort is a better choice than bubble sort
>> in almost all cases, but saying insertion sort is simpler than
>> bubble sort is an apples-and-oranges comparison.
>
> For common definitions of what bubble and insertion sorts are,
> insertion sorts are simpler.
>
> Standard versions in C:
>
> void InsertionSort(int a[], int length)
> {
>     int i, j, temp;
>
>     for(i = 1; i < length; i++)
>     {
>         temp = a[i];
>         for (j = i - 1; j >= 0 && a[j] > temp; j--)
>             a[j + 1] = a[j];
>         a[j] = temp;
>     }
> }
>
> void BubbleSort(int a[], int length)
> {
>     int i, j, temp;
>
>     for (i = 0; i < length; i++)
>     {
>         for (j = 0; j < length - i - 1; j++)
>         {
>             if (a[j + 1] < a[j])
>             {
>                 temp = a[j];
>                 a[j] = a[j + 1];
>                 a[j + 1] = temp;
>             }
>         }
>     }
> }
>
> There's not a lot of difference there (basically all the same
> lines of code, except that the "if" in the bubble sort has been
> folded into insertion sort's inner loop termination test).

The first function body is shorter but that doesn't mean it is
simpler.  The loop invariants in the first function are more
complicated than those in the second function.  Also I think
you're being unfair in how the two function bodies are written.
In most cases bubble sort is presented using a "swap()" function
to exchange two elements.  There are a few other deficiencies,
relative to how the InsertionSort function is written, for the
coding in the BubbleSort function.  It's easy, and I think more
usual, to present bubble sort something like this:

    void BubbleSort(int a[], int length)
    {
      int n, i;

      for (n = length; n > 1; n--)
        for (i = 1; i < n; i++)
          if (a[i-1] < a[i])
            swap( a, i-1, i );
    }

Writing bubble sort this way also illustrates a key difference
between the two:  swap() is a simple and easy-to-understand
abstraction.  There is no analogous abstraction for the key
operation in insertion sort.  That lack isn't just accidental.

> But there's little to add to the insertion sort, while the bubble
> sort is usually enhanced by adding a check to stop if no swapping
> has been done in a pass, adding more code (and if you don't, the
> usual claim that bubble sort works well on already sorted files is
> false).  [...]

More apples-and-oranges.  Of course bubble sort can be enhanced
in that way, but the main point of doing so is to show that the
enhancement doesn't buy much.  In contrast, the common follow-on
to insertion sort -- using binary search to find the insertion
point -- offers a significant theoretical (and often practical)
advantage, in that there is now an O( n log n ) bound on the
number of comparisons done.  No one is arguing that bubble sort
is a better practical choice for actual coding;  insertion sort
is clearly better, on several different axes.  But supporting
that argument by claiming insertion sort is simpler than bubble
sort is overreaching.  It's better, in the sense of making a more
convincing argument, to admit that bubble sort is simpler, and
then go on to explain that despite the relative simplicity of
bubble sort, insertion sort (or sometimes others, depending on
circumstances) is a better practical choice, for several reasons
that are compelling and also clearly defensible.

Thread

C++ threshold for "stupid" sorting algorithms (O(n^2)) Soviet_Mario <SovietMario@CCCP.MIR> - 2020-01-01 13:17 +0100
  Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-01 13:25 +0100
    Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-01-01 17:33 +0000
      Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-05 03:54 +0100
        Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-05 04:04 +0100
        Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2020-01-05 03:59 +0000
          Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-05 05:03 +0100
            Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Soviet_Mario <SovietMario@CCCP.MIR> - 2020-01-05 21:13 +0100
              Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-06 05:50 +0100
              Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-06 06:55 +0100
        Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-01-05 04:20 +0000
          Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-05 05:26 +0100
            Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-01-05 13:33 +0000
              Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-05 15:01 +0100
                Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-01-05 22:26 +0000
                Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-06 05:39 +0100
                Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Öö Tiib <ootiib@hot.ee> - 2020-01-05 23:54 -0800
                Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-06 08:59 +0100
                Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Öö Tiib <ootiib@hot.ee> - 2020-01-06 01:02 -0800
                Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Jorgen Grahn <grahn+nntp@snipabacken.se> - 2020-01-06 09:34 +0000
                Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-06 10:36 +0100
                Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Öö Tiib <ootiib@hot.ee> - 2020-01-06 03:33 -0800
                Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-06 12:59 +0100
                Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-01-06 22:54 +0000
                Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-07 04:57 +0100
                Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Melzzzzz <Melzzzzz@zzzzz.com> - 2020-01-07 07:51 +0000
          Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Melzzzzz <Melzzzzz@zzzzz.com> - 2020-01-05 15:16 +0000
        Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-05 05:50 +0100
  Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bo Persson <bo@bo-persson.se> - 2020-01-01 13:34 +0100
    Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Soviet_Mario <SovietMario@CCCP.MIR> - 2020-01-01 14:09 +0100
      Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bo Persson <bo@bo-persson.se> - 2020-01-01 15:16 +0100
  Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Robert Wessel <robertwessel2@yahoo.com> - 2020-01-01 09:24 -0600
    Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Soviet_Mario <SovietMario@CCCP.MIR> - 2020-01-01 17:12 +0100
      Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Öö Tiib <ootiib@hot.ee> - 2020-01-02 15:11 -0800
    Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-01-10 13:53 -0800
      Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Robert Wessel <robertwessel2@yahoo.com> - 2020-01-10 16:45 -0600
        Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-01-21 03:11 -0800
          Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-01-21 15:04 +0000
            Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-01-27 11:52 -0800
              Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-01-30 00:32 +0000
                Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-02-15 05:30 -0800
                Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-02-15 16:39 +0000
  Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Christian Gollwitzer <auriocus@gmx.de> - 2020-01-02 11:28 +0100
    Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Soviet_Mario <SovietMario@CCCP.MIR> - 2020-01-02 19:46 +0100
      Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-02 20:00 +0100
        Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-03 07:37 +0100
        Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Soviet_Mario <SovietMario@CCCP.MIR> - 2020-01-03 20:06 +0100
          Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Öö Tiib <ootiib@hot.ee> - 2020-01-03 11:12 -0800
            Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Soviet_Mario <SovietMario@CCCP.MIR> - 2020-01-04 17:58 +0100
          Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) David Brown <david.brown@hesbynett.no> - 2020-01-03 21:25 +0100
            Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Melzzzzz <Melzzzzz@zzzzz.com> - 2020-01-03 21:00 +0000

csiph-web