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

Groups > comp.lang.c++ > #70923 > unrolled thread

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

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

Contents

  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

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

#71173

>> Give me a URL to a paper that proves this.

> Miserable attempt of hiding being caught being liar noted.
> It is just quite common with real world data that it was entered in sorted order
> or that some other part of system already sorted it.
> <https://en.wikipedia.org/wiki/Sorting_algorithm#Efficient_sorts>
> "Second, the algorithms often perform poorly on already sorted data or almost
> sorted data – these are common in real-world data, and can be sorted in O(n)
> time by appropriate algorithms."

That's not a proof on the heuristics of chosen sorting algorithms.

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

#71175

On Monday, 6 January 2020 11:36:12 UTC+2, Bonita Montero  wrote:
> >> Give me a URL to a paper that proves this.
> 
> > Miserable attempt of hiding being caught being liar noted.
> > It is just quite common with real world data that it was entered in sorted order
> > or that some other part of system already sorted it.
> > <https://en.wikipedia.org/wiki/Sorting_algorithm#Efficient_sorts>
> > "Second, the algorithms often perform poorly on already sorted data or almost
> > sorted data – these are common in real-world data, and can be sorted in O(n)
> > time by appropriate algorithms."
> 
> That's not a proof on the heuristics of chosen sorting algorithms.

So what? As system designer you should have good idea what kind of
data from what kinds of sources it processes. So asking for formal
statistical proofs indicates cluenesness.  

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

#71176

>>> Miserable attempt of hiding being caught being liar noted.
>>> It is just quite common with real world data that it was entered in sorted order
>>> or that some other part of system already sorted it.
>>> <https://en.wikipedia.org/wiki/Sorting_algorithm#Efficient_sorts>
>>> "Second, the algorithms often perform poorly on already sorted data or almost
>>> sorted data – these are common in real-world data, and can be sorted in O(n)
>>> time by appropriate algorithms."

>> That's not a proof on the heuristics of chosen sorting algorithms.

> So what? As system designer you should have good idea what kind of
> data from what kinds of sources it processes. So asking for formal
> statistical proofs indicates cluenesness.

If you imagine for what purposes the one or the other algoritm might be
suitable you don't find out how often the one or the other is actually
needed in real projects. So you're clueness here as you suggest it is
possible to find out this the way you describe.

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

#71182

Bonita Montero <Bonita.Montero@gmail.com> writes:

>>> Try the fixed code. The fixed code gives this with gcc on my computer:
>
>> No apology for accusing me of lying I see.
>> The fixed code does not alter what I said: the simple sort is faster for
>> all your test sizes for some data sets -- specifically when the data are
>> already sorted.  The factor is now smaller (no longer always greater
>> than 2) but still between 1.5 and 2.
>
> The discussion wasn't about presorted datasets and that's not usual.

You made the discussion about (a) a sweeping statement of yours that was
untrue, and (b) your calling me a liar for make a true statement.

-- 
Ben.

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

#71184

> You made the discussion about (a) a sweeping statement of yours that
> was untrue, and (b) your calling me a liar for make a true statement.

Because you're so stupid to trust any code.

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

#71189

On 2020-01-07, Bonita Montero <Bonita.Montero@gmail.com> wrote:
>> You made the discussion about (a) a sweeping statement of yours that
>> was untrue, and (b) your calling me a liar for make a true statement.
>
> Because you're so stupid to trust any code.
Hey, buffon, I see you are egomaniacal still.

-- 
press any key to continue or any other to quit...
U ničemu ja ne uživam kao u svom statusu INVALIDA -- Zli Zec
Svi smo svedoci - oko 3 godine intenzivne propagande je dovoljno da jedan narod poludi --  Zli Zec
Na divljem zapadu i nije bilo tako puno nasilja, upravo zato jer su svi 
bili naoruzani. -- Mladen Gogala

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

#71147

On 2020-01-05, Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
> Bonita Montero <Bonita.Montero@gmail.com> writes:
>
>>>>> In your experience, what is (roughly) a reasonable threshold (n) in
>>>>> terms of convenience of passing from stupid algorithms (bubblesort,
>>>>> gnomesort) to better and more complex ones ?
>>
>>>> Don't use the simpler algorithms. Algthough they might be faster
>>>> on a few elements, their runtime doesn't count then because there
>>>> are just a few elements.
>>
>>> But there might be billions of such small sorts.  It's a rare situation,
>>> but it shows that the logic you used is not sound.
>>
>> Try this on your computer.
>
> First, I was commenting on your logic, not your conclusion.  Your
> conclusion -- don't use simple but slow sorts -- might be right but you
> can't get to that conclusion using the logic you used.
>
> Second, the results from your timing code will depend on the data as
> well as on the algorithm.  For example, on my laptop, with sorted data,
> your code (slightly modified to use non-random numbers) shows bubble
> sort as faster (by a factor of at least 2) for all sizes tested (you go
> up to 20).  I don't know if the code is measuring this correctly -- I am
> just reporting on the output.
>
> Third, the OP was not just about bubble sort.  To get a sound answer
> from measurements, the best simple sort, insertion sort, should be used.

I use quicksort then insertion sort when partition falls down bellow 15
elements...
I think this is common knowledge.
>
><cut timing code>


-- 
press any key to continue or any other to quit...
U ničemu ja ne uživam kao u svom statusu INVALIDA -- Zli Zec
Svi smo svedoci - oko 3 godine intenzivne propagande je dovoljno da jedan narod poludi --  Zli Zec
Na divljem zapadu i nije bilo tako puno nasilja, upravo zato jer su svi 
bili naoruzani. -- Mladen Gogala

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

#71134

Little bug:

>      for( size_t c = 2; c <= SIZE; ++c )
>      {
>          start = high_resolution_clock::now();
>          for( size_t r = ROUNDS; r != 0; --r )
>              copy( vRef.begin(), vRef.begin() + c, vSort.begin() ),
>              bubblesort( vSort.begin(), vSort.end() );
                bubblesort( vSort.begin(), vSort.begin() + c );
>          bsNs = (uint64_t)duration_cast<nanoseconds>( 
> high_resolution_clock::now() - start ).count();
>          start = high_resolution_clock::now();
>          for( size_t r = ROUNDS; r != 0; --r )
>              copy( vRef.begin(), vRef.begin() + c, vSort.begin() ),
>              sort( vSort.begin(), vSort.end() );
 >              sort( vSort.begin(), vSort.begin() + c );
>          sNs = (uint64_t)duration_cast<nanoseconds>( 
> high_resolution_clock::now() - start ).count();
>          cout << "size:\t" << c << "\tbs:\t" << bsNs / 1.0E6 << "\ts:\t" 
> << sNs / 1.0E6 << endl;
>      }

Before I measured always the same block-size.
With that code now bubblesort is faster up to 6 elements.

size:	2	bs:	0.3522	s:	0.9208
size:	3	bs:	0.4927	s:	1.0144
size:	4	bs:	0.9208	s:	1.6702
size:	5	bs:	1.2458	s:	1.6793
size:	6	bs:	1.6039	s:	2.1342
size:	7	bs:	2.0537	s:	1.9543
size:	8	bs:	2.4752	s:	2.6737
size:	9	bs:	3.1595	s:	3.0331
size:	10	bs:	3.7429	s:	3.187
size:	11	bs:	4.4821	s:	3.4102
size:	12	bs:	5.5326	s:	4.0687
size:	13	bs:	7.0794	s:	4.2507
size:	14	bs:	7.0796	s:	4.6087
size:	15	bs:	9.5706	s:	5.3354
size:	16	bs:	10.4491	s:	5.8877
size:	17	bs:	13.0148	s:	5.9372
size:	18	bs:	13.8979	s:	7.4023
size:	19	bs:	16.1734	s:	7.5393
size:	20	bs:	18.0571	s:	8.0887

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

#70925

On 2020-01-01 at 13:17, Soviet_Mario wrote:
> In your experience, what is (roughly) a reasonable threshold (n) in 
> terms of convenience of passing from stupid algorithms (bubblesort, 
> gnomesort) to better and more complex ones ?
> 
> I know this depends a lot also on HW.
> 

It also depends on the data that is to be sorted.

For example, if the data is already almost correctly sorted, that will 
be the best case for bubblesort but the worst case for quicksort.

So, it depends.


     Bo Persson

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

#70926

On 01/01/2020 13:34, Bo Persson wrote:
> On 2020-01-01 at 13:17, Soviet_Mario wrote:
>> In your experience, what is (roughly) a reasonable 
>> threshold (n) in terms of convenience of passing from 
>> stupid algorithms (bubblesort, gnomesort) to better and 
>> more complex ones ?
>>
>> I know this depends a lot also on HW.
>>
> 
> It also depends on the data that is to be sorted.
> 
> For example, if the data is already almost correctly sorted, 
> that will be the best case for bubblesort but the worst case 
> for quicksort.

I won't even be able to write a stable version of quick sort :\

> 
> So, it depends.
> 
> 
>      Bo Persson
> 
> 
> 


-- 
1) Resistere, resistere, resistere.
2) Se tutti pagano le tasse, le tasse le pagano tutti
Soviet_Mario - (aka Gatto_Vizzato)

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

#70928

On 2020-01-01 at 14:09, Soviet_Mario wrote:
> On 01/01/2020 13:34, Bo Persson wrote:
>> On 2020-01-01 at 13:17, Soviet_Mario wrote:
>>> In your experience, what is (roughly) a reasonable threshold (n) in 
>>> terms of convenience of passing from stupid algorithms (bubblesort, 
>>> gnomesort) to better and more complex ones ?
>>>
>>> I know this depends a lot also on HW.
>>>
>>
>> It also depends on the data that is to be sorted.
>>
>> For example, if the data is already almost correctly sorted, that will 
>> be the best case for bubblesort but the worst case for quicksort.
> 
> I won't even be able to write a stable version of quick sort :\
> 

No, of course not.

Just saying that there are cases where a "stupid" algorithm can be O(n) 
and a "smart" one be O(n^2). And that it can be data dependent, and not 
just depend on the size.

That might make it hard to find a useful general threshold.


     Bo Persson

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

#70930

On Wed, 1 Jan 2020 13:17:09 +0100, Soviet_Mario <SovietMario@CCCP.MIR>
wrote:

>In your experience, what is (roughly) a reasonable threshold 
>(n) in terms of convenience of passing from stupid 
>algorithms (bubblesort, gnomesort) to better and more 
>complex ones ?
>
>I know this depends a lot also on HW.
>
>But to write down an order of magnitude, I'm talking about 
>small data sets (some tens to at worst some hundredth, never 
>above 1000).
>
>With such small figures, I was thinking that even the most 
>simple O(n^2) bubble or gnome could be acceptable.
>But I've no experience in real comparison.
>
>The application is not performance intensive, at least for 
>this operations which would be performed only a few times
>
>
>I did not mention that the algorithm HAS TO BE "stable" : 
>not to move equally ranked items (in order to allow tables 
>to be sorted by multiple keys)


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

But you're posting this is a C++ forum.  std::stable_sort short be
your first choice for such a requirement.  The first question is why
*not* use the library function?  If you think it's only for
containers, that's wrong, you can use std::begin and std::end to
process a normal array.

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

#70934

On 01/01/2020 16:24, Robert Wessel wrote:
> On Wed, 1 Jan 2020 13:17:09 +0100, Soviet_Mario <SovietMario@CCCP.MIR>
> wrote:
> 
>> In your experience, what is (roughly) a reasonable threshold
>> (n) in terms of convenience of passing from stupid
>> algorithms (bubblesort, gnomesort) to better and more
>> complex ones ?
>>
>> I know this depends a lot also on HW.
>>
>> But to write down an order of magnitude, I'm talking about
>> small data sets (some tens to at worst some hundredth, never
>> above 1000).
>>
>> With such small figures, I was thinking that even the most
>> simple O(n^2) bubble or gnome could be acceptable.
>> But I've no experience in real comparison.
>>
>> The application is not performance intensive, at least for
>> this operations which would be performed only a few times
>>
>>
>> I did not mention that the algorithm HAS TO BE "stable" :
>> not to move equally ranked items (in order to allow tables
>> to be sorted by multiple keys)
> 
> 
> 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).
> 
> But you're posting this is a C++ forum.  std::stable_sort short be

gulp ! I did not even know it existed ... I will try to see 
if I'm able to apply to struct data (where the sorting is to 
be done by a specialized comparison operator o function)

yes a built-in function would be a lot appreciated.

I used to use vectors <type> on some IDEs .... but on some 
others, QT for example, now I only find another kind of 
vector template, requiring not only a type, but also an 
"allocator" (and I don't know what to pass as argument, I'd 
just prefer the general purpose allocator). Dunno why only 
these new vectors are provided.

> your first choice for such a requirement.  The first question is why
> *not* use the library function? 

I did not know about :)

> If you think it's only for
> containers, that's wrong, you can use std::begin and std::end to
> process a normal array.

I find it more readable to be able to use
operator [] (int Index)
actually

> 


-- 
1) Resistere, resistere, resistere.
2) Se tutti pagano le tasse, le tasse le pagano tutti
Soviet_Mario - (aka Gatto_Vizzato)

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

#70985

On Wednesday, 1 January 2020 18:13:02 UTC+2, Soviet_Mario  wrote:
> 
> I used to use vectors <type> on some IDEs .... but on some 
> others, QT for example, now I only find another kind of 
> vector template, requiring not only a type, but also an 
> "allocator" (and I don't know what to pass as argument, I'd 
> just prefer the general purpose allocator). Dunno why only 
> these new vectors are provided.

Vector has been always such. 

On usual case (over 99% of code) we do not provide that second
argument since it has default value that is very rarely worth to
change. Allocators are complex topic so these can be learned later.

That default value is std::allocator<T> on case of std::vector
and std::pmr::polymorphic_allocator<T> on case of std::pmr::vector
(that is in standard since C++17).

It is odd when IDE somehow requires entry of allocator, maybe
find out what you did in settings that caused it and try to turn
the behavior off.
 

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

#71266

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.

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

#71268

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).  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).  If you do the swap test
in bubble sort you can simplify the outer loop, but a fair cost in
performance for unsorted inputs.

Enhancement to both are possible (if somewhat pointless), but often
result in what's usually considered a different sort.  Using a binary
search to determine the insertion point, or working the bubble sort
from both ends result in binary insertion and cocktail shaker sorts,
for example.

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

#71482

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.

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

#71488

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);

and some people would not call your example bubble sort because it has
no "almost sorted" advantage.  These discussions often end up a bit
ungrounded because the terms are not exact.

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.

<cut>
-- 
Ben.

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

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

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

#71649

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

<cut lots>

I left this a few days in the hope that I'd have something interesting
to say about it since your post was itself interesting and clearly not
trivial to write.  Unfortunately I failed, but such a thoughtful post
merits a reply, even if the reply is not thoughtful.

-- 
Ben.

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

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

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

csiph-web