Path: csiph.com!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c++
Subject: Re: C++ threshold for "stupid" sorting algorithms (O(n^2))
Date: Mon, 27 Jan 2020 11:52:08 -0800
Organization: A noiseless patient Spider
Lines: 299
Message-ID: <86imkwhe3b.fsf@linuxsc.com>
References: <qui2k6$rst$1@dont-email.me> <ukdp0ftld5mrph4p9q1sht942f4vvedak8@4ax.com> <86k15z3rm7.fsf@linuxsc.com> <fauh1ftsjuopokhmi3287165drd5ue2ku3@4ax.com> <86iml5jc79.fsf@linuxsc.com> <87y2u0am1m.fsf@bsb.me.uk>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: reader02.eternal-september.org; posting-host="7c306968cf7022673062d49c54d79376"; logging-data="10131"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19diMcJqmZeMKeVq+WJjhCgRSeICxP4Hy8="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:B62E/LCtKY3OOFTy/3uGhl4eStU= sha1:AbArkC3aMHOkRKSvCDTKsInv0J4=
Xref: csiph.com comp.lang.c++:71628

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

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
>> Robert Wessel <robertwessel2@yahoo.com> writes:
>
> <cut>
>
>>> 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.
>
> Some people would say you can write insertion sort using only swap:
>
>   for (int i = 1; i < length; i++)
>     for (int j = i; j > 0 && a[j-1] < a[j]; j--)
>       swap(a, j-1, j);

Yes.  I too think that's reasonable.  It isn't how I would
usually write an insertion sort, but presenting it as one
way of writing insertion sort is appropriate IMO.

> and some people would not call your example bubble sort because it
> has no "almost sorted" advantage.

Yes, I acknowledge that.  It kind of surprised me when I first
heard it but it is obviously true (that is, that some people
would have that reaction).  As a double check on my own usage I
consulted two acquaintances, with different backgrounds, and
phrasing the question as neutrally as I could.  Both of them
answered the way I would (i.e., that early termination is not
essential to be termed bubble sort), but all that proves is only
that different people mean somewhat different things when they
talk about it.

> These discussions often end up a bit ungrounded because the
> terms are not exact.

Certainly they often do end up a bit ungrounded.  I might say
that's largely because different people define the terms slightly
differently and also vary in how much latitude they are willing
to accept.  I myself tend to fall in the more tolerant admission
in this area.  But the main thing is I think we agree on the key
point, that it's hard to reach a shared conclusion because people
bring with them (and sometimes unconsciously) different working
assumptions.

> And if you don't want to do the insert using swaps, why not write
> an insert function?  In what way would that not be an easy-to
> understand abstraction?  Although insert is more complex that
> swap, it has the effect of cutting the complexity of the sort
> function in half:  one loops inserts each element into a growing
> sorted array;  inserting each element needs a simple loop.

Let me try to respond to this paragraph more all-at-once than a
sentence at a time.

First I think all your statements and questions are reasonable.
Writing a separate function to perform insertions clearly can
help simplify the overall algorithm.  I suppose the same sort of
thing might be doable with bubble sort, but it's less obvious
how much benefit that would bring.

I suspect a large part of the difficulty we have in reconciling
our different points of view comes from how we characterize the
different sorting algorithms and how we measure "simpleness".  My
view of things like sorting algorithms tends to be conceptual:  I
remember (what I think are) the essential elements, generally the
fewer the better, and forget the details because for me it's
usually easier to reconstruct them than remember them.  The
central component of bubble sort (as I conceptualize it, in case
that needs saying) is comparing and possibly swapping adjacent
elements.  The central component of insertion sort is finding and
moving an element into the appropriate place of an already sorted
subarray.  (Sorry for the poor phrasing there.)  Insertion isn't
a very complicated abstraction but it's a "larger" abstraction
than swapping - it involves a larger part of the element array,
and in a qsort-like setting needs the comparison function, which
swap does not.

Summarizing by example:  for me a cocktail sort (which I learned as
a "brick and bubble" sort) is really just a bubble sort;  that the
"bubbles" are going two different directions doesn't change that.
For deciding which is simpler, I think bubble sort is simpler
because I think the "central operation" (swap versus insert) is
easier to explain to an eight year old.  I will grant you that both
of these views are both personal and subjective.  Perhaps part of
my point is to get the personalness and subjectiveness out into the
open rather than hidden behind seemingly absolute statements.

Let me run now through several revisions of a function that shows
a way of coding a sorting algorithm that I might call bubble
sort.  All of these writings have the property that early
termination (that is, in time closer to O(N) than to O(N log N)
will occur for some set of inputs that are close to being sorted.
I wrote all these myself, in the order shown, but not exactly
with a clear destination in mind.  So some of my comments below
have the benefit of hindsight, although the algorithms themselves
mostly don't.

(Incidental note:  I use functions 'backwards()' and 'exchange()'
for purposes of comparing and swapping, respectively.  This was
done to allow instrumentation and measurement.)

First, the most simple-minded version:

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

      start:
        for(  i = 1;  i < n;  i++  ){
            if(  backwards( a, i-1, i )  ){
                exchange( a, i-1, i );
                goto  start;
            }
        }
    }

In descriptive English:  look for the first out-of-order pair.
If one is found, put them in order, and simply start again from
the beginning.

(Historical note:  this version of bubble sort was actually used
for a common command in a popular OS of the late 1960's and early
1970's.  Fortunately it was sorting a very limited number of
items.)

I think this is great place to start an explanation of bubble
sort, because the code is both easy to understand and obviously
works correctly.  IMO the 'goto' actually helps the presentation,
at least for the first version, but let's bow to structured
tradition and eliminate it.  Doing this is straightforward:

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

        for(  i = 1;  i < n;  i++  ){
            if(  backwards( a, i-1, i )  ){
                exchange( a, i-1, i );
                i = 0;
            }
        }
    }

Now suitably goto-free, but both of these have an awful property:
the usual running time is not even O(N*N) but O(N*N*N).  Terrible!
To improve that, we might observe that when the out-of-order pair
is reached, all the ones before it haven't changed and so don't
need to be looked at again.  What has changed is a[i-1], so we
should go back and look at a[i-2] and a[i-1] -- assuming, that is,
that there /is/ an a[i-2];  if i is less than 2 we can simply go
forward.  This ideas gives the next revision:

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

        for(  i = 1;  i < n;  i++  ){
            if(  backwards( a, i-1, i )  ){
                exchange( a, i-1, i );
                if(  i > 1  )  i -= 2;
            }
        }
    }

This "minor" change is surprisingly effective.  Not only has the
running time improved from O(N*N*N) to O(N*N), but it does early
termination quite well.  On scrambled inputs it's competitive with
the Knuth version of bubble sort (sometimes better, sometimes
worse), and on "nearly sorted" inputs it does well on a larger set
of inputs than the Knuth bubble sort.  It needs more explanation
to show that it's correct, which of course is usually the cost
of a fancier algorithm.

Besides being faster on more nearly sorted inputs, this version
behaves much like other bubble sorts.  In particular it uses about
twice as many compares as (linear) insertion sort.  The "bubbles"
are mostly "sinking" rather than "rising", but for me that doesn't
change things enough to make a difference.

(Please also see the note at the bottom regarding this function.)

We can make a further improvement by noting a simlar property in
the other direction.  After finding an out-of-order pair, and
dragging the smaller element down to its appropriate depth, there
is no need check the elements between there and where we first
found it.  We add a variable 'next_i' to remember the high water
mark, and use 'next_i++' whenever we switch directions from
"downwards" to "upwards".  Here is the code:

    void
    even_better_bubble_sort( int a[], int n ){
        int i = 1, next_i = 2;

        while(  i < n  ){
            if(  backwards( a, i-1, i )  ){
                exchange( a, i-1, i );
                i = i > 1 ? i-1 : next_i++;
            } else {
                i = next_i++;
            }
        }
    }

Probably because of how I arrived at this refinement, I thought of
it as an enhanced bubble sort.  Then I ran my little test harness,
and was surprised to see that it does exactly the same number of
compares as (linear) insertion sort.  In retrospect, naturally, I
can see that what is being done here is isomorphic to a swapping
insertion sort.  But it wasn't what I was expecting when I first
coded it.  I hope at least that the journey was interesting.

Two further comments.  First is that I coded up all these version
myself without consulting any references.  It was only after I had
written all of them (and run the measurements) that I learned from
a friend that what I call here "better_bubble_sort()" is known
more widely as "Gnome sort".  So that was serendipitous.

My closing comment gets back to comparing the two sorting methods.
If we contrast the last two functions, what I think stands out is
the extra work done to allow the skipping of comparisons between
the sink point and the high water mark.  To me this difference both
shows why insertion sort runs faster than bubble sort and also
demonstrates that insertion sort is more elaborate than bubble
sort:  more mechanism is needed, which requires more explanation,
but that additional mechanism is what gives insertion sort its
speed advantage over bubble sort.  I admit the conclusion is both
personal and subjective.  To me it still seems right because it
isn't what I set out to do - my motivation was only to present a
series of algorithms that I would all call bubble sort, to show
what I mean when I use the term.  I was actually very surprised
when I saw that the last version had the same behavior as does
insertion sort.

Sorry this has ended up being so long, and again I hope it was
at least interesting.