Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #71488
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Newsgroups | comp.lang.c++ |
| Subject | Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) |
| Date | 2020-01-21 15:04 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <87y2u0am1m.fsf@bsb.me.uk> (permalink) |
| References | <qui2k6$rst$1@dont-email.me> <ukdp0ftld5mrph4p9q1sht942f4vvedak8@4ax.com> <86k15z3rm7.fsf@linuxsc.com> <fauh1ftsjuopokhmi3287165drd5ue2ku3@4ax.com> <86iml5jc79.fsf@linuxsc.com> |
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.
Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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