Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #147130 > unrolled thread
| Started by | DFS <nospam@dfs.com> |
|---|---|
| First post | 2019-10-20 18:12 -0400 |
| Last post | 2019-10-29 15:15 +0100 |
| Articles | 20 on this page of 114 — 19 participants |
Back to article view | Back to comp.lang.c
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 5 of 6 — ← Prev page 1 2 3 4 [5] 6 Next page →
| From | Malcolm McLean <malcolm.arthur.mclean@gmail.com> |
|---|---|
| Date | 2019-10-29 03:05 -0700 |
| Message-ID | <0ea78690-4f14-4a02-b74b-edead3f4ace6@googlegroups.com> |
| In reply to | #147320 |
On Tuesday, 29 October 2019 01:32:34 UTC, Bart wrote:
>
> (Actually the I-sort was taken from a source on-line that called it
> 'insertion sort':
> https://www.tutorialspoint.com/data_structures_algorithms/insertion_sort_algorithm.htm.
>
> While their version of 'bubble sort' isn't that different from mine.)
>
Their version is this.
begin BubbleSort(list)
for all elements of list
if list[i] > list[i+1]
swap(list[i], list[i+1])
end if
end for
end BubbleSort
That's not bubble sort. Bubblesort is this.
begin BubbleSort(list)
boolean flag = true;
while(flag)
flag = false;
for all elements of list
if(list[i] > list[i+1])
{
swap(list[i], list[i+1]);
flag = true;
}
end for
end while
return list
end BubbleSort
You set a flag if you make a swap, and terminate when no swaps are made
(the array is sorted). The flag adds several extra lines to the implementation.
Not everything posted on the internet is right.
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2019-10-29 11:12 +0000 |
| Message-ID | <x8VtF.50270$7ei.41700@fx36.am4> |
| In reply to | #147324 |
On 29/10/2019 10:05, Malcolm McLean wrote:
> On Tuesday, 29 October 2019 01:32:34 UTC, Bart wrote:
>>
>> (Actually the I-sort was taken from a source on-line that called it
>> 'insertion sort':
>> https://www.tutorialspoint.com/data_structures_algorithms/insertion_sort_algorithm.htm.
>>
>> While their version of 'bubble sort' isn't that different from mine.)
>>
>
> Their version is this.
>
> begin BubbleSort(list)
>
> for all elements of list
> if list[i] > list[i+1]
> swap(list[i], list[i+1])
> end if
> end for
> end BubbleSort
>
>
> That's not bubble sort. Bubblesort is this.
>
> begin BubbleSort(list)
>
> boolean flag = true;
>
> while(flag)
>
> flag = false;
> for all elements of list
> if(list[i] > list[i+1])
> {
> swap(list[i], list[i+1]);
> flag = true;
> }
> end for
> end while
>
> return list
>
> end BubbleSort
>
> You set a flag if you make a swap, and terminate when no swaps are made
> (the array is sorted). The flag adds several extra lines to the implementation.
>
>
> Not everything posted on the internet is right.
You should have read a bit further. After 'Algorithm', which as you say
describes one iteration that they have wrongly called BubbleSort, they
have 'Pseudo Code', which shows the more fleshed out version:
(https://www.tutorialspoint.com/data_structures_algorithms/bubble_sort_algorithm.htm)
------------------------------------------------
procedure bubbleSort( list : array of items )
loop = list.count;
for i = 0 to loop-1 do:
swapped = false
for j = 0 to loop-1 do:
/* compare the adjacent elements */
if list[j] > list[j+1] then
/* swap them */
swap( list[j], list[j+1] )
swapped = true
end if
end for
/*if no number was swapped that means
array is sorted now, break the loop.*/
if(not swapped) then
break
end if
end for
end procedure return list
------------------------------------------------
I decided to test this, by first changing just enough syntax to match my
test language (where 'loop' and 'list' are keywords, for a start).
I found that that there was a bug (for 0-based, that second 'loop-1' is
off-by-one). Also that, with the flag, there is no need for the outer
for-loop, it just needs a while or repeat loop, but it means the flag
can optionally be removed and it will still work, just be much slower
for nearly-sorted data.
But with minimal fixes (changing loop-1 to loop-2), the following
[interpreted] code can sort both 5000 random elements and 50000000
sorted elements in 1 second (comments elided):
------------------------------------------------
proc bubbleSort( lst )=
enum(false=0,true)
loopx := lst.len;
for i := 0 to loopx-1 do
swapped := false
for j := 0 to loopx-2 do
if lst[j] > lst[j+1] then
swap( lst[j], lst[j+1] )
swapped := true
end if
end for
if(not swapped) then
exit
end if
end for
end proc
------------------------------------------------
So that page needs some attention, but the essence of a bubble sort is
there.
[toc] | [prev] | [next] | [standalone]
| From | already5chosen@yahoo.com |
|---|---|
| Date | 2019-10-29 04:19 -0700 |
| Message-ID | <8d68b129-1a29-46d6-a3b0-d896bf52fbc4@googlegroups.com> |
| In reply to | #147324 |
On Tuesday, October 29, 2019 at 12:06:07 PM UTC+2, Malcolm McLean wrote:
> On Tuesday, 29 October 2019 01:32:34 UTC, Bart wrote:
> >
> > (Actually the I-sort was taken from a source on-line that called it
> > 'insertion sort':
> > https://www.tutorialspoint.com/data_structures_algorithms/insertion_sort_algorithm.htm.
> >
> > While their version of 'bubble sort' isn't that different from mine.)
> >
>
> Their version is this.
>
> begin BubbleSort(list)
>
> for all elements of list
> if list[i] > list[i+1]
> swap(list[i], list[i+1])
> end if
> end for
> end BubbleSort
>
>
> That's not bubble sort. Bubblesort is this.
>
> begin BubbleSort(list)
>
> boolean flag = true;
>
> while(flag)
>
> flag = false;
> for all elements of list
> if(list[i] > list[i+1])
> {
> swap(list[i], list[i+1]);
> flag = true;
> }
> end for
> end while
>
> return list
>
> end BubbleSort
>
> You set a flag if you make a swap, and terminate when no swaps are made
> (the array is sorted). The flag adds several extra lines to the implementation.
>
>
> Not everything posted on the internet is right.
Including your post above.
For me the statement "for all elements of list" means "in any order". That's not a bubblesort. Bublesort typically works in ascending order of indices. Descending order will do too. But not an arbitrary order.
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2019-10-29 11:47 +0000 |
| Message-ID | <9FVtF.442$Q26.244@fx34.am4> |
| In reply to | #147326 |
On 29/10/2019 11:19, already5chosen@yahoo.com wrote:
> On Tuesday, October 29, 2019 at 12:06:07 PM UTC+2, Malcolm McLean wrote:
>> On Tuesday, 29 October 2019 01:32:34 UTC, Bart wrote:
>>>
>>> (Actually the I-sort was taken from a source on-line that called it
>>> 'insertion sort':
>>> https://www.tutorialspoint.com/data_structures_algorithms/insertion_sort_algorithm.htm.
>>>
>>> While their version of 'bubble sort' isn't that different from mine.)
>>>
>>
>> Their version is this.
>>
>> begin BubbleSort(list)
>>
>> for all elements of list
>> if list[i] > list[i+1]
>> swap(list[i], list[i+1])
>> end if
>> end for
>> end BubbleSort
>>
>>
>> That's not bubble sort. Bubblesort is this.
>>
>> begin BubbleSort(list)
>>
>> boolean flag = true;
>>
>> while(flag)
>>
>> flag = false;
>> for all elements of list
>> if(list[i] > list[i+1])
>> {
>> swap(list[i], list[i+1]);
>> flag = true;
>> }
>> end for
>> end while
>>
>> return list
>>
>> end BubbleSort
>>
>> You set a flag if you make a swap, and terminate when no swaps are made
>> (the array is sorted). The flag adds several extra lines to the implementation.
>>
>>
>> Not everything posted on the internet is right.
>
> Including your post above.
> For me the statement "for all elements of list" means "in any order". That's not a bubblesort. Bublesort typically works in ascending order of indices. Descending order will do too. But not an arbitrary order.
>
That's nit-picking. 'Forall' is often used in languages to iterate
through all elements of a list or collection in order. Others just use
'for' for the same purpose:
for x in L:
Where is the order (either ascending or descending) specified? It isn't.
It is just understood that that is how it works.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.arthur.mclean@gmail.com> |
|---|---|
| Date | 2019-10-29 05:03 -0700 |
| Message-ID | <8abd3fc2-468c-4cf4-8adc-0f0f3337d3d2@googlegroups.com> |
| In reply to | #147328 |
On Tuesday, 29 October 2019 11:47:25 UTC, Bart wrote:
> On 29/10/2019 11:19, already5chosen@yahoo.com wrote:
> > On Tuesday, October 29, 2019 at 12:06:07 PM UTC+2, Malcolm McLean wrote:
> >> On Tuesday, 29 October 2019 01:32:34 UTC, Bart wrote:
> >>>
> >>> (Actually the I-sort was taken from a source on-line that called it
> >>> 'insertion sort':
> >>> https://www.tutorialspoint.com/data_structures_algorithms/insertion_sort_algorithm.htm.
> >>>
> >>> While their version of 'bubble sort' isn't that different from mine.)
> >>>
> >>
> >> Their version is this.
> >>
> >> begin BubbleSort(list)
> >>
> >> for all elements of list
> >> if list[i] > list[i+1]
> >> swap(list[i], list[i+1])
> >> end if
> >> end for
> >> end BubbleSort
> >>
> >>
> >> That's not bubble sort. Bubblesort is this.
> >>
> >> begin BubbleSort(list)
> >>
> >> boolean flag = true;
> >>
> >> while(flag)
> >>
> >> flag = false;
> >> for all elements of list
> >> if(list[i] > list[i+1])
> >> {
> >> swap(list[i], list[i+1]);
> >> flag = true;
> >> }
> >> end for
> >> end while
> >>
> >> return list
> >>
> >> end BubbleSort
> >>
> >> You set a flag if you make a swap, and terminate when no swaps are made
> >> (the array is sorted). The flag adds several extra lines to the implementation.
> >>
> >>
> >> Not everything posted on the internet is right.
> >
> > Including your post above.
> > For me the statement "for all elements of list" means "in any order". That's not a bubblesort. Bublesort typically works in ascending order of indices. Descending order will do too. But not an arbitrary order.
> >
>
> That's nit-picking. 'Forall' is often used in languages to iterate
> through all elements of a list or collection in order. Others just use
> 'for' for the same purpose:
>
> for x in L:
>
> Where is the order (either ascending or descending) specified? It isn't.
> It is just understood that that is how it works.
>
I followed the pseudo code of the webpage.
But a problem with those languages that include a "for all" or "for each"
type statement is that often you need the index for further calculations.
As with a sort routine.
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2019-10-29 13:16 +0000 |
| Message-ID | <oYWtF.542$WE5.287@fx30.am4> |
| In reply to | #147329 |
On 29/10/2019 12:03, Malcolm McLean wrote:
> On Tuesday, 29 October 2019 11:47:25 UTC, Bart wrote:
>> That's nit-picking. 'Forall' is often used in languages to iterate
>> through all elements of a list or collection in order. Others just use
>> 'for' for the same purpose:
>>
>> for x in L:
>>
>> Where is the order (either ascending or descending) specified? It isn't.
>> It is just understood that that is how it works.
>>
> I followed the pseudo code of the webpage.
>
> But a problem with those languages that include a "for all" or "for each"
> type statement is that often you need the index for further calculations.
> As with a sort routine.
It's possible; eg in Python:
a=[10,20,30]
for (i,x) in enumerate(a):
print(i,x)
which displays:
0 10
1 20
2 30
Or in one of mine:
a:=(10,20,30)
forall i,x in a do
println i,x # indices will be 1,2,3
od
C of course doesn't need anything special, provided everything is int:
int a[]={10,20,30};
for (int i=0, x=a[0]; i<sizeof(a)/sizeof(a[0]); ++i, x=a[i]) {
printf("%d %d\n", i, x);
}
(Some possible UB here though.)
I agree that the pseudo-code on the tutorialspoint site was poor for
bubble sort; for insertion sort it was much better.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2019-10-29 17:13 +0000 |
| Message-ID | <877e4npj9b.fsf@bsb.me.uk> |
| In reply to | #147328 |
Bart <bc@freeuk.com> writes: > On 29/10/2019 11:19, already5chosen@yahoo.com wrote: >> On Tuesday, October 29, 2019 at 12:06:07 PM UTC+2, Malcolm McLean wrote: <cut> >>> for all elements of list >>> if(list[i] > list[i+1]) <cut> >>> Not everything posted on the internet is right. >> >> Including your post above. >> For me the statement "for all elements of list" means "in any >> order". That's not a bubblesort. Bublesort typically works in >> ascending order of indices. Descending order will do too. But not an >> arbitrary order. >> > > That's nit-picking. 'Forall' is often used in languages to iterate > through all elements of a list or collection in order. At the very least it shows that there is ambiguity. That's the trouble with pseudo-code. But here's a real nit: if (as we seem to be assuming) i runs over "all elements of list", list[i] and list[i+1] can't both be valid. I'd not come across www.tutorialspoint.com before but the pages I've seen recently (the two sorting ones and memset) don't leave a good impression. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2019-10-29 17:35 +0000 |
| Message-ID | <bL_tF.3377$Q26.2982@fx34.am4> |
| In reply to | #147336 |
On 29/10/2019 17:13, Ben Bacarisse wrote:
> Bart <bc@freeuk.com> writes:
>
>> On 29/10/2019 11:19, already5chosen@yahoo.com wrote:
>>> On Tuesday, October 29, 2019 at 12:06:07 PM UTC+2, Malcolm McLean wrote:
> <cut>
>>>> for all elements of list
>>>> if(list[i] > list[i+1])
> <cut>
>>>> Not everything posted on the internet is right.
>>>
>>> Including your post above.
>>> For me the statement "for all elements of list" means "in any
>>> order". That's not a bubblesort. Bublesort typically works in
>>> ascending order of indices. Descending order will do too. But not an
>>> arbitrary order.
>>>
>>
>> That's nit-picking. 'Forall' is often used in languages to iterate
>> through all elements of a list or collection in order.
>
> At the very least it shows that there is ambiguity. That's the trouble
> with pseudo-code.
>
> But here's a real nit: if (as we seem to be assuming) i runs over "all
> elements of list", list[i] and list[i+1] can't both be valid.
Yes, that particular pseudo-code is sloppy, and it doesn't say how 'i'
comes about. Actually i iterates over indices (not values) and excludes
the last element.
(This is an advantage of using a real language for pseudo-code, but at a
level where it is not full of trivial details which is the point of
using pseudo-code. And why I sometimes use mine for that purpose. In
mine I could say:
for i in init(A)
which does exactly the above. However it uses 'init', named after the
Haskell function that drops the last element; and 'for' that iterates
over indices rather then 'forall' that iterates over values, which is a
too subtle difference.
Most clear and most universally understood would be:
for i:=1 to A.len-1
But it still leaves the question of being 1-based or 0-based something
that has to be stated separately (I had to infer it).)
[toc] | [prev] | [next] | [standalone]
| From | Ike Naar <ike@sdf.lonestar.org> |
|---|---|
| Date | 2019-10-30 07:19 +0000 |
| Message-ID | <slrn3g50qrieca.9dm.ike@sdf.lonestar.org> |
| In reply to | #147324 |
On 2019-10-29, Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote: > for all elements of list > if(list[i] > list[i+1]) Does 'for all elements of list' include the last element of list? Is 'list[i+1]' well-defined for the last element of the list?
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2019-10-29 16:19 +0000 |
| Message-ID | <87d0efplr5.fsf@bsb.me.uk> |
| In reply to | #147320 |
Bart <bc@freeuk.com> writes:
> On 29/10/2019 01:09, Ben Bacarisse wrote:
>> Bart <bc@freeuk.com> writes:
>>
>>> On 28/10/2019 23:59, Ben Bacarisse wrote:
>>>> Bart <bc@freeuk.com> writes:
>>>
>>>>> With a 'swapped' flag as I'd normally use it, both are fast when data
>>>>> is already sorted. Without that flag, it's only suitable for very
>>>>> small data sets.
>>>>
>>>> But that was not the algorithm you've been championing!
>>>
>>> I showed the one without the early stop because you complained that
>>> bubble sort needed the early stop flag.
>>
>> No I didn't.
>>
>>>> Please show
>>>> this better bubble sort so we can all see what you think is
>>>> aesthetically pleasing about that code. It will help to clarify what
>>>> rage of alternatives you accept whilst still keeping bubble sort "more
>>>> consistent" than insertion sort.
>>>
>>> Here are the 3 sorts we've been discussing
>>
>> No, these are not the sorts we have been discussing. For most of the
>> thread I've been discussion a sort you posted about that is not bubble
>> sort and is not one of the three you've shown here. And the insertion
>> sort that I have been talking about is not one of them either.
>
> You're being hard.
>
> If that B-sort isn't bubble-sort (whatever that officially needs to
> comprise) and that I-sort isn't insertion-sort, then I must have
> invented my very own sort algorithms!
I don't think you are being serious now. Look at what I wrote.
You started by championing a sort (which is not bubble sort despite) the
just tested ~n**2 times an swapped as needed. You praised it's
memorability and it's locality in testing and swapping. So I showed you
an insertion sort that is more efficient, just as memorable, and also
has locality of testing and swapping. You've never discussed it because
it does not fit your narrative.
And when it became clear that insertion sort handles nearly sorted lists
"out of the box", you ditched the terrible sort you originally
championed and switched to actual bubble sort.
>> This is comp.lang.c. I've been talking about C code. I'm not going to
>> post sorting code in a language unknown to me in any group, and
>> certainly not here.
> If you really need to see C code,
I don't need to see C code. I said I won't post sorting code in a
language unknown to me, that's all.
> I posted runnable versions of my insertion and quick sort earlier on
> Monday. While what /I/ call bubble sort (obviously not what you
> consider bubble sort)
Don't be silly. Of course this is bubble sort (once the bug is removed)
and I never said otherwise. That's the whole point. It's not the
algorithm you started off championing.
> can be illustrated with this fragment:
>
> do {
> swapped=0;
> for (i=1; i<n; ++i) {
> if (data[i]>data[i+1]) {
You probably intended to compare data[i-1] and data[i], or maybe you
intended the loop to have different bounds, but one way or another
something is wrong here.
> swapped=1;
> t=data[i];
> data[i]=data[i+1];
> data[i+1]=t;
> }
> }
At this point you can decrease n (or otherwise adjust the loop upper
bound).
> } while (swapped);
--
Ben.
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2019-10-29 16:50 +0000 |
| Message-ID | <C5_tF.1958$oK6.1034@fx07.am4> |
| In reply to | #147332 |
On 29/10/2019 16:19, Ben Bacarisse wrote:
> Bart <bc@freeuk.com> writes:
>> If that B-sort isn't bubble-sort (whatever that officially needs to
>> comprise) and that I-sort isn't insertion-sort, then I must have
>> invented my very own sort algorithms!
>
> I don't think you are being serious now. Look at what I wrote.
>
> You started by championing a sort (which is not bubble sort despite) the
> just tested ~n**2 times an swapped as needed. You praised it's
> memorability and it's locality in testing and swapping. So I showed you
> an insertion sort that is more efficient, just as memorable, and also
> has locality of testing and swapping. You've never discussed it because
> it does not fit your narrative.
>
> And when it became clear that insertion sort handles nearly sorted lists
> "out of the box", you ditched the terrible sort you originally
> championed and switched to actual bubble sort.
I consider the early exit flag an optional tweak.
>> can be illustrated with this fragment:
>>
>> do {
>> swapped=0;
>> for (i=1; i<n; ++i) {
>> if (data[i]>data[i+1]) {
>
> You probably intended to compare data[i-1] and data[i], or maybe you
(I think this is adapted from a 1-based algorithm but the array is still
1-based in C, with element 0 ignored and an extra element at the end.
Since this is part of a benchmark for compilers, this was an unimportant
detail but I missed it before posting.)
> intended the loop to have different bounds, but one way or another
> something is wrong here.
>
>> swapped=1;
>> t=data[i];
>> data[i]=data[i+1];
>> data[i+1]=t;
>> }
>> }
>
> At this point you can decrease n (or otherwise adjust the loop upper
> bound).
Thanks, that makes bubble-sort (interpreted version) 35% faster for
random data. That's a version with a swapped/sorted flag, although it
makes little difference for random data. (Actually, removing the flag
made it a further 7% faster.)
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.arthur.mclean@gmail.com> |
|---|---|
| Date | 2019-10-29 10:03 -0700 |
| Message-ID | <53ee934f-fc36-46db-82e1-f669ec125f10@googlegroups.com> |
| In reply to | #147333 |
On Tuesday, 29 October 2019 16:50:54 UTC, Bart wrote: > On 29/10/2019 16:19, Ben Bacarisse wrote: > > Bart <bc@freeuk.com> writes: > > >> If that B-sort isn't bubble-sort (whatever that officially needs to > >> comprise) and that I-sort isn't insertion-sort, then I must have > >> invented my very own sort algorithms! > > > > I don't think you are being serious now. Look at what I wrote. > > > > You started by championing a sort (which is not bubble sort despite) the > > just tested ~n**2 times an swapped as needed. You praised it's > > memorability and it's locality in testing and swapping. So I showed you > > an insertion sort that is more efficient, just as memorable, and also > > has locality of testing and swapping. You've never discussed it because > > it does not fit your narrative. > > > > And when it became clear that insertion sort handles nearly sorted lists > > "out of the box", you ditched the terrible sort you originally > > championed and switched to actual bubble sort. > > I consider the early exit flag an optional tweak. > I'd regard it as crucial. With brute force swapping sort, you have to realise that after N passes through the loop, the data must be sorted. With bubblesort with the flag, you stop when there are no swaps left and the data is sorted. So it's fundamentally different logic.
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2019-10-29 17:13 +0000 |
| Message-ID | <Uq_tF.7736$Fr3.6649@fx39.am4> |
| In reply to | #147334 |
On 29/10/2019 17:03, Malcolm McLean wrote: > On Tuesday, 29 October 2019 16:50:54 UTC, Bart wrote: >> On 29/10/2019 16:19, Ben Bacarisse wrote: >>> Bart <bc@freeuk.com> writes: >> >>>> If that B-sort isn't bubble-sort (whatever that officially needs to >>>> comprise) and that I-sort isn't insertion-sort, then I must have >>>> invented my very own sort algorithms! >>> >>> I don't think you are being serious now. Look at what I wrote. >>> >>> You started by championing a sort (which is not bubble sort despite) the >>> just tested ~n**2 times an swapped as needed. You praised it's >>> memorability and it's locality in testing and swapping. So I showed you >>> an insertion sort that is more efficient, just as memorable, and also >>> has locality of testing and swapping. You've never discussed it because >>> it does not fit your narrative. >>> >>> And when it became clear that insertion sort handles nearly sorted lists >>> "out of the box", you ditched the terrible sort you originally >>> championed and switched to actual bubble sort. >> >> I consider the early exit flag an optional tweak. >> > I'd regard it as crucial. With brute force swapping sort, you have to > realise that after N passes through the loop, the data must be sorted. > With bubblesort with the flag, you stop when there are no swaps left > and the data is sorted. So it's fundamentally different logic. Well yes, the data will be sorted after N-1 passes. (N=1 requires no passes; N=2 requires 1; etc). Removing the flag still requires an outer loop.
[toc] | [prev] | [next] | [standalone]
| From | already5chosen@yahoo.com |
|---|---|
| Date | 2019-10-29 10:23 -0700 |
| Message-ID | <6bca01ee-02e3-424f-9b43-09d50cea0a93@googlegroups.com> |
| In reply to | #147334 |
On Tuesday, October 29, 2019 at 7:03:35 PM UTC+2, Malcolm McLean wrote: > On Tuesday, 29 October 2019 16:50:54 UTC, Bart wrote: > > On 29/10/2019 16:19, Ben Bacarisse wrote: > > > Bart <bc@freeuk.com> writes: > > > > >> If that B-sort isn't bubble-sort (whatever that officially needs to > > >> comprise) and that I-sort isn't insertion-sort, then I must have > > >> invented my very own sort algorithms! > > > > > > I don't think you are being serious now. Look at what I wrote. > > > > > > You started by championing a sort (which is not bubble sort despite) the > > > just tested ~n**2 times an swapped as needed. You praised it's > > > memorability and it's locality in testing and swapping. So I showed you > > > an insertion sort that is more efficient, just as memorable, and also > > > has locality of testing and swapping. You've never discussed it because > > > it does not fit your narrative. > > > > > > And when it became clear that insertion sort handles nearly sorted lists > > > "out of the box", you ditched the terrible sort you originally > > > championed and switched to actual bubble sort. > > > > I consider the early exit flag an optional tweak. > > > I'd regard it as crucial. With brute force swapping sort, you have to > realise that after N passes through the loop, the data must be sorted. > With bubblesort with the flag, you stop when there are no swaps left > and the data is sorted. So it's fundamentally different logic. I'd rather record the point of last swap. It's the same cost as setting the flag. On the next iteration I'd run an inner loop until the point of the last swap. Intuitively it seems that such variant would be measurably faster when input array contains only few elements that are out of order. Esp. in the case where there is only one such element.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2019-10-29 22:20 +0000 |
| Message-ID | <87y2x3nqhd.fsf@bsb.me.uk> |
| In reply to | #147337 |
already5chosen@yahoo.com writes: > On Tuesday, October 29, 2019 at 7:03:35 PM UTC+2, Malcolm McLean wrote: >> On Tuesday, 29 October 2019 16:50:54 UTC, Bart wrote: >> > On 29/10/2019 16:19, Ben Bacarisse wrote: >> > > Bart <bc@freeuk.com> writes: >> > >> > >> If that B-sort isn't bubble-sort (whatever that officially needs to >> > >> comprise) and that I-sort isn't insertion-sort, then I must have >> > >> invented my very own sort algorithms! >> > > >> > > I don't think you are being serious now. Look at what I wrote. >> > > >> > > You started by championing a sort (which is not bubble sort despite) the >> > > just tested ~n**2 times an swapped as needed. You praised it's >> > > memorability and it's locality in testing and swapping. So I showed you >> > > an insertion sort that is more efficient, just as memorable, and also >> > > has locality of testing and swapping. You've never discussed it because >> > > it does not fit your narrative. >> > > >> > > And when it became clear that insertion sort handles nearly sorted lists >> > > "out of the box", you ditched the terrible sort you originally >> > > championed and switched to actual bubble sort. >> > >> > I consider the early exit flag an optional tweak. >> > >> I'd regard it as crucial. With brute force swapping sort, you have to >> realise that after N passes through the loop, the data must be sorted. >> With bubblesort with the flag, you stop when there are no swaps left >> and the data is sorted. So it's fundamentally different logic. > > I'd rather record the point of last swap. It's the same cost as > setting the flag. On the next iteration I'd run an inner loop until > the point of the last swap. Intuitively it seems that such variant > would be measurably faster when input array contains only few elements > that are out of order. Esp. in the case where there is only one such > element. This is Knuth's "Algorithm B (Bubble sort)" in 5.2.2 of TACP. In fact, it's the only thing he calls Bubble sort. I've done a few tests and it does not seem to make much difference compared to the version that just decrements the inner loop upper bound on each pass. With one or two randomly out of order elements it is sometimes faster and sometimes slower. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | already5chosen@yahoo.com |
|---|---|
| Date | 2019-10-30 03:04 -0700 |
| Message-ID | <a07666a8-1e1e-4920-9f0f-d8538b9c9437@googlegroups.com> |
| In reply to | #147349 |
On Wednesday, October 30, 2019 at 12:20:53 AM UTC+2, Ben Bacarisse wrote: > already5chosen@yahoo.com writes: > > > On Tuesday, October 29, 2019 at 7:03:35 PM UTC+2, Malcolm McLean wrote: > >> On Tuesday, 29 October 2019 16:50:54 UTC, Bart wrote: > >> > On 29/10/2019 16:19, Ben Bacarisse wrote: > >> > > Bart <bc@freeuk.com> writes: > >> > > >> > >> If that B-sort isn't bubble-sort (whatever that officially needs to > >> > >> comprise) and that I-sort isn't insertion-sort, then I must have > >> > >> invented my very own sort algorithms! > >> > > > >> > > I don't think you are being serious now. Look at what I wrote. > >> > > > >> > > You started by championing a sort (which is not bubble sort despite) the > >> > > just tested ~n**2 times an swapped as needed. You praised it's > >> > > memorability and it's locality in testing and swapping. So I showed you > >> > > an insertion sort that is more efficient, just as memorable, and also > >> > > has locality of testing and swapping. You've never discussed it because > >> > > it does not fit your narrative. > >> > > > >> > > And when it became clear that insertion sort handles nearly sorted lists > >> > > "out of the box", you ditched the terrible sort you originally > >> > > championed and switched to actual bubble sort. > >> > > >> > I consider the early exit flag an optional tweak. > >> > > >> I'd regard it as crucial. With brute force swapping sort, you have to > >> realise that after N passes through the loop, the data must be sorted. > >> With bubblesort with the flag, you stop when there are no swaps left > >> and the data is sorted. So it's fundamentally different logic. > > > > I'd rather record the point of last swap. It's the same cost as > > setting the flag. On the next iteration I'd run an inner loop until > > the point of the last swap. Intuitively it seems that such variant > > would be measurably faster when input array contains only few elements > > that are out of order. Esp. in the case where there is only one such > > element. > > This is Knuth's "Algorithm B (Bubble sort)" in 5.2.2 of TACP. In fact, > it's the only thing he calls Bubble sort. > > I've done a few tests and it does not seem to make much difference > compared to the version that just decrements the inner loop upper bound > on each pass. With one or two randomly out of order elements it is > sometimes faster and sometimes slower. > > -- > Ben. That's results I wouldn't expect. What are you sorting? Are we still talking about arrays of pointers to relatively short strings (1-16 characters with ~5 as an average length) with strcasecmp() as comparison function? Or something else? And how long your arrays are?
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2019-10-30 15:39 +0000 |
| Message-ID | <87h83qnsqk.fsf@bsb.me.uk> |
| In reply to | #147356 |
already5chosen@yahoo.com writes: > On Wednesday, October 30, 2019 at 12:20:53 AM UTC+2, Ben Bacarisse wrote: >> already5chosen@yahoo.com writes: >> >> > On Tuesday, October 29, 2019 at 7:03:35 PM UTC+2, Malcolm McLean wrote: >> >> On Tuesday, 29 October 2019 16:50:54 UTC, Bart wrote: >> >> > On 29/10/2019 16:19, Ben Bacarisse wrote: >> >> > > Bart <bc@freeuk.com> writes: >> >> > >> >> > >> If that B-sort isn't bubble-sort (whatever that officially needs to >> >> > >> comprise) and that I-sort isn't insertion-sort, then I must have >> >> > >> invented my very own sort algorithms! >> >> > > >> >> > > I don't think you are being serious now. Look at what I wrote. >> >> > > >> >> > > You started by championing a sort (which is not bubble sort despite) the >> >> > > just tested ~n**2 times an swapped as needed. You praised it's >> >> > > memorability and it's locality in testing and swapping. So I showed you >> >> > > an insertion sort that is more efficient, just as memorable, and also >> >> > > has locality of testing and swapping. You've never discussed it because >> >> > > it does not fit your narrative. >> >> > > >> >> > > And when it became clear that insertion sort handles nearly sorted lists >> >> > > "out of the box", you ditched the terrible sort you originally >> >> > > championed and switched to actual bubble sort. >> >> > >> >> > I consider the early exit flag an optional tweak. >> >> > >> >> I'd regard it as crucial. With brute force swapping sort, you have to >> >> realise that after N passes through the loop, the data must be sorted. >> >> With bubblesort with the flag, you stop when there are no swaps left >> >> and the data is sorted. So it's fundamentally different logic. >> > >> > I'd rather record the point of last swap. It's the same cost as >> > setting the flag. On the next iteration I'd run an inner loop until >> > the point of the last swap. Intuitively it seems that such variant >> > would be measurably faster when input array contains only few elements >> > that are out of order. Esp. in the case where there is only one such >> > element. >> >> This is Knuth's "Algorithm B (Bubble sort)" in 5.2.2 of TACP. In fact, >> it's the only thing he calls Bubble sort. >> >> I've done a few tests and it does not seem to make much difference >> compared to the version that just decrements the inner loop upper bound >> on each pass. With one or two randomly out of order elements it is >> sometimes faster and sometimes slower. >> > That's results I wouldn't expect. > What are you sorting? Are we still talking about arrays of pointers to > relatively short strings (1-16 characters with ~5 as an average > length) with strcasecmp() as comparison function? Or something else? > And how long your arrays are? Sorry, way too little thought went into my tests and I then gave too little data about them! My test harness sorts integers, but it can use an expensive compare operation by converting them to strings. For pretty much any length of almost-sorted array there is not much in it when using the native integer >. The Knuth version does, on average, fewer comparisons, but the loop logic is slightly more complex and the two often seem to balance out. But with an expensive string compare of the integers, the Knuth version is, indeed, always faster, and you can make it faster by any amount you like by making the compare as expensive as you like. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.arthur.mclean@gmail.com> |
|---|---|
| Date | 2019-10-30 09:02 -0700 |
| Message-ID | <b601a278-9149-40ca-baa7-ac905d675efe@googlegroups.com> |
| In reply to | #147363 |
On Wednesday, 30 October 2019 15:44:30 UTC, Ben Bacarisse wrote: > > For pretty much any length of almost-sorted array there is not much in > it when using the native integer >. The Knuth version does, on average, > fewer comparisons, but the loop logic is slightly more complex and the > two often seem to balance out. But with an expensive string compare of > the integers, the Knuth version is, indeed, always faster, and you can > make it faster by any amount you like by making the compare as expensive > as you like. > You're unlikely to want to sort a list of integers in the real code. Far more likely to want to sort a list of records on a field. So swaps relatively expensive. Also, though the field you sort on may well be an integer, if the sort routine has to take a qsort() style function pointer, the comparison is via an indirect call and so quite expensive.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2019-10-30 19:35 +0000 |
| Message-ID | <874kzqni1b.fsf@bsb.me.uk> |
| In reply to | #147366 |
Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: > On Wednesday, 30 October 2019 15:44:30 UTC, Ben Bacarisse wrote: >> >> For pretty much any length of almost-sorted array there is not much in >> it when using the native integer >. The Knuth version does, on average, >> fewer comparisons, but the loop logic is slightly more complex and the >> two often seem to balance out. But with an expensive string compare of >> the integers, the Knuth version is, indeed, always faster, and you can >> make it faster by any amount you like by making the compare as expensive >> as you like. >> > You're unlikely to want to sort a list of integers in the real code. Far > more likely to want to sort a list of records on a field. So swaps > relatively expensive. The test harness has a configurable size for the data objects so that the cost of swaps can be varied. If the swap cost goes up, the relative cost of comparison will go down. <cut> -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | already5chosen@yahoo.com |
|---|---|
| Date | 2019-10-30 14:11 -0700 |
| Message-ID | <54740e2a-2881-482c-ad58-620dcfb80111@googlegroups.com> |
| In reply to | #147363 |
On Wednesday, October 30, 2019 at 5:44:30 PM UTC+2, Ben Bacarisse wrote:
> already5chosen@yahoo.com writes:
>
> > On Wednesday, October 30, 2019 at 12:20:53 AM UTC+2, Ben Bacarisse wrote:
> >> already5chosen@yahoo.com writes:
> >>
> >> > On Tuesday, October 29, 2019 at 7:03:35 PM UTC+2, Malcolm McLean wrote:
> >> >> On Tuesday, 29 October 2019 16:50:54 UTC, Bart wrote:
> >> >> > On 29/10/2019 16:19, Ben Bacarisse wrote:
> >> >> > > Bart <bc@freeuk.com> writes:
> >> >> >
> >> >> > >> If that B-sort isn't bubble-sort (whatever that officially needs to
> >> >> > >> comprise) and that I-sort isn't insertion-sort, then I must have
> >> >> > >> invented my very own sort algorithms!
> >> >> > >
> >> >> > > I don't think you are being serious now. Look at what I wrote.
> >> >> > >
> >> >> > > You started by championing a sort (which is not bubble sort despite) the
> >> >> > > just tested ~n**2 times an swapped as needed. You praised it's
> >> >> > > memorability and it's locality in testing and swapping. So I showed you
> >> >> > > an insertion sort that is more efficient, just as memorable, and also
> >> >> > > has locality of testing and swapping. You've never discussed it because
> >> >> > > it does not fit your narrative.
> >> >> > >
> >> >> > > And when it became clear that insertion sort handles nearly sorted lists
> >> >> > > "out of the box", you ditched the terrible sort you originally
> >> >> > > championed and switched to actual bubble sort.
> >> >> >
> >> >> > I consider the early exit flag an optional tweak.
> >> >> >
> >> >> I'd regard it as crucial. With brute force swapping sort, you have to
> >> >> realise that after N passes through the loop, the data must be sorted.
> >> >> With bubblesort with the flag, you stop when there are no swaps left
> >> >> and the data is sorted. So it's fundamentally different logic.
> >> >
> >> > I'd rather record the point of last swap. It's the same cost as
> >> > setting the flag. On the next iteration I'd run an inner loop until
> >> > the point of the last swap. Intuitively it seems that such variant
> >> > would be measurably faster when input array contains only few elements
> >> > that are out of order. Esp. in the case where there is only one such
> >> > element.
> >>
> >> This is Knuth's "Algorithm B (Bubble sort)" in 5.2.2 of TACP. In fact,
> >> it's the only thing he calls Bubble sort.
> >>
> >> I've done a few tests and it does not seem to make much difference
> >> compared to the version that just decrements the inner loop upper bound
> >> on each pass. With one or two randomly out of order elements it is
> >> sometimes faster and sometimes slower.
> >>
> > That's results I wouldn't expect.
>
> > What are you sorting? Are we still talking about arrays of pointers to
> > relatively short strings (1-16 characters with ~5 as an average
> > length) with strcasecmp() as comparison function? Or something else?
> > And how long your arrays are?
>
> Sorry, way too little thought went into my tests and I then gave too
> little data about them!
>
> My test harness sorts integers, but it can use an expensive compare
> operation by converting them to strings.
>
> For pretty much any length of almost-sorted array there is not much in
> it when using the native integer >. The Knuth version does, on average,
> fewer comparisons, but the loop logic is slightly more complex and the
> two often seem to balance out. But with an expensive string compare of
> the integers, the Knuth version is, indeed, always faster, and you can
> make it faster by any amount you like by making the compare as expensive
> as you like.
>
> --
> Ben.
Just to be sure that we are talking about the same thing.
That's the code for what you call "native comparison":
void bubblesort_Ben(int x[], int nElem)
{
while (nElem > 1) {
int swapped = 0;
for (int i = 1; i < nElem; ++i) {
if (x[i-1] > x[i]) {
int temp = x[i-1];
x[i-1] = x[i];
x[i] = temp;
swapped = 1;
}
}
if (!swapped)
break;
--nElem;
}
}
void bubblesort_Don(int x[], int nElem)
{
while (nElem > 1) {
int next_nElem = 0;
for (int i = 1; i < nElem; ++i) {
if (x[i-1] > x[i]) {
int temp = x[i-1];
x[i-1] = x[i];
x[i] = temp;
next_nElem = i;
}
}
nElem = next_nElem;
}
}
And that's what we expect optimizing compiler will do out of it:
void bubblesort_Ben_opt(int x[], int nElem)
{
while (nElem > 1) {
int swapped = 0;
int prev = x[0];
for (int i = 1; i < nElem; ++i) {
int next = x[i];
if (prev > next) {
x[i-1] = next;
x[i] = prev;
next = prev;
swapped = 1;
}
prev = next;
}
if (!swapped)
break;
--nElem;
}
}
void bubblesort_Don_opt(int x[], int nElem)
{
while (nElem > 1) {
int next_nElem = 0;
int prev = x[0];
for (int i = 1; i < nElem; ++i) {
int next = x[i];
if (prev > next) {
x[i-1] = next;
x[i] = prev;
next = prev;
next_nElem = i;
}
prev = next;
}
nElem = next_nElem;
}
}
I still don't see why an inner loop of 'Ben' variant can be faster than inner loop of 'Don' variant. To me they look the same.
[toc] | [prev] | [next] | [standalone]
Page 5 of 6 — ← Prev page 1 2 3 4 [5] 6 Next page →
Back to top | Article view | comp.lang.c
csiph-web