Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #74757 > unrolled thread
| Started by | G G <gdotone@gmail.com> |
|---|---|
| First post | 2015-11-03 06:31 -0800 |
| Last post | 2015-11-20 10:43 +0000 |
| Articles | 20 on this page of 167 — 29 participants |
Back to article view | Back to comp.lang.c
Is it possible C is the security problem? G G <gdotone@gmail.com> - 2015-11-03 06:31 -0800
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-03 14:57 +0000
Re: Is it possible C is the security problem? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2015-11-03 15:04 +0000
Re: Is it possible C is the security problem? G G <gdotone@gmail.com> - 2015-11-03 07:11 -0800
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-03 15:25 +0000
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-03 20:13 +0000
Re: Is it possible C is the security problem? Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-11-03 15:18 -0500
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-03 20:34 +0000
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-03 22:47 +0000
Re: Is it possible C is the security problem? Udyant Wig <udyantw@gmail.com> - 2015-11-04 15:36 +0530
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-04 10:34 +0000
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-03 15:18 -0800
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-03 17:42 -0800
Re: Is it possible C is the security problem? Geoff <geoff@invalid.invalid> - 2015-11-03 15:32 -0800
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-03 23:57 +0000
Re: Is it possible C is the security problem? Geoff <geoff@invalid.invalid> - 2015-11-03 21:13 -0800
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-04 07:22 +0000
Re: Is it possible C is the security problem? David Brown <david.brown@hesbynett.no> - 2015-11-04 11:32 +0100
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-04 10:54 +0000
Re: Is it possible C is the security problem? David Brown <david.brown@hesbynett.no> - 2015-11-04 13:38 +0100
Re: Is it possible C is the security problem? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2015-11-07 08:27 +0000
Re: Is it possible C is the security problem? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2015-11-05 09:26 +0000
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-05 10:03 +0000
Re: Is it possible C is the security problem? James Kuyper <jameskuyper@verizon.net> - 2015-11-05 08:53 -0500
Re: Is it possible C is the security problem? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2015-11-06 10:04 +0000
Re: Is it possible C is the security problem? Reinhardt Behm <rbehm@hushmail.com> - 2015-11-05 21:06 +0800
Re: Is it possible C is the security problem? Keith Thompson <kst-u@mib.org> - 2015-11-05 11:14 -0800
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-05 11:44 -0800
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-07 02:43 -0800
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-07 17:30 -0800
Re: Is it possible C is the security problem? raltbos@xs4all.nl (Richard Bos) - 2015-11-10 16:35 +0000
Re: Is it possible C is the security problem? Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-11-10 11:52 -0500
Re: Is it possible C is the security problem? Robert Wessel <robertwessel2@yahoo.com> - 2015-11-11 00:48 -0600
Re: Is it possible C is the security problem? raltbos@xs4all.nl (Richard Bos) - 2015-11-17 21:55 +0000
Re: Is it possible C is the security problem? Robert Wessel <robertwessel2@yahoo.com> - 2015-11-17 19:14 -0600
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-18 03:40 +0000
Re: Is it possible C is the security problem? Robert Wessel <robertwessel2@yahoo.com> - 2015-11-17 23:01 -0600
Re: Is it possible C is the security problem? Keith Thompson <kst-u@mib.org> - 2015-11-18 09:00 -0800
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-18 09:09 -0800
Re: Is it possible C is the security problem? Robert Wessel <robertwessel2@yahoo.com> - 2015-11-18 15:35 -0600
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-18 21:35 +0000
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-18 20:38 -0800
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-19 05:40 +0000
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-18 22:55 -0800
Re: Is it possible C is the security problem? Ian Collins <ian-news@hotmail.com> - 2015-11-19 19:56 +1300
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-18 23:40 -0800
Re: Is it possible C is the security problem? Ian Collins <ian-news@hotmail.com> - 2015-11-19 21:05 +1300
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-19 06:40 -0800
Re: Is it possible C is the security problem? asetofsymbols@gmail.com - 2015-11-19 11:37 -0800
Re: Is it possible C is the security problem? asetofsymbols@gmail.com - 2015-11-19 12:09 -0800
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-19 12:52 -0800
Re: Is it possible C is the security problem? Ian Collins <ian-news@hotmail.com> - 2015-11-20 12:20 +1300
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-19 15:34 -0800
Re: Is it possible C is the security problem? Ian Collins <ian-news@hotmail.com> - 2015-11-22 16:43 +1300
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-21 21:28 -0800
Re: Is it possible C is the security problem? Ian Collins <ian-news@hotmail.com> - 2015-11-22 20:51 +1300
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-22 07:26 -0800
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-22 09:42 -0800
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-22 09:59 -0800
Re: Is it possible C is the security problem? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-23 07:08 +0000
Re: Is it possible C is the security problem? Ian Collins <ian-news@hotmail.com> - 2015-11-23 11:57 +1300
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-22 16:06 -0800
Re: Is it possible C is the security problem? Ian Collins <ian-news@hotmail.com> - 2015-11-23 13:26 +1300
Re: Is it possible C is the security problem? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-19 09:09 +0000
Re: Is it possible C is the security problem? Keith Thompson <kst-u@mib.org> - 2015-11-20 02:29 -0800
Re: Is it possible C is the security problem? raltbos@xs4all.nl (Richard Bos) - 2015-11-20 12:33 +0000
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-20 09:26 -0800
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-19 13:37 +0000
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-19 14:07 -0800
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-20 01:38 +0000
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-19 18:43 -0800
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-20 12:09 +0000
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-20 01:48 -0800
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-20 11:16 +0000
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-20 05:04 -0800
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-20 18:18 +0000
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-20 11:55 -0800
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-21 00:27 +0000
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-20 18:57 -0800
Re: Is it possible C is the security problem? Keith Thompson <kst-u@mib.org> - 2015-11-20 19:50 -0800
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-20 20:06 -0800
Re: Is it possible C is the security problem? Keith Thompson <kst-u@mib.org> - 2015-11-20 20:46 -0800
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-20 20:56 -0800
Re: Is it possible C is the security problem? Robert Wessel <robertwessel2@yahoo.com> - 2015-11-21 04:58 -0600
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-21 04:59 -0800
Re: Is it possible C is the security problem? Robert Wessel <robertwessel2@yahoo.com> - 2015-11-21 13:26 -0600
Re: Is it possible C is the security problem? Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-11-21 14:38 -0500
Re: Is it possible C is the security problem? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-21 06:49 +0000
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-20 22:56 -0800
Re: Is it possible C is the security problem? Robert Wessel <robertwessel2@yahoo.com> - 2015-11-21 04:36 -0600
Re: Is it possible C is the security problem? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-21 06:44 +0000
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-21 15:59 +0000
Re: Is it possible C is the security problem? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-21 18:33 +0000
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-21 19:19 +0000
Re: Is it possible C is the security problem? Robert Wessel <robertwessel2@yahoo.com> - 2015-11-21 13:33 -0600
Re: Is it possible C is the security problem? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-22 14:42 +0000
Re: Is it possible C is the security problem? Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-22 14:17 -0800
Re: Is it possible C is the security problem? Ian Collins <ian-news@hotmail.com> - 2015-11-20 14:51 +1300
Re: Is it possible C is the security problem? Robert Wessel <robertwessel2@yahoo.com> - 2015-11-19 08:06 -0600
Re: Is it possible C is the security problem? Robert Wessel <robertwessel2@yahoo.com> - 2015-11-18 15:40 -0600
Re: Is it possible C is the security problem? Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-20 13:57 -0800
Re: Is it possible C is the security problem? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-21 06:56 +0000
Re: Is it possible C is the security problem? Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-23 03:16 -0800
Re: Is it possible C is the security problem? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-23 22:28 +0000
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-23 21:11 -0800
Re: Is it possible C is the security problem? Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-24 10:29 -0800
Re: Is it possible C is the security problem? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-25 02:38 +0000
Re: Is it possible C is the security problem? Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-27 13:54 -0800
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-10 10:23 -0800
Re: Is it possible C is the security problem? Keith Thompson <kst-u@mib.org> - 2015-11-10 11:21 -0800
Re: Is it possible C is the security problem? Melzzzzz <mel@zzzzz.com> - 2015-11-04 00:58 +0100
Re: Is it possible C is the security problem? Les Cargill <lcargill99@comcast.com> - 2015-11-03 18:26 -0600
Re: Is it possible C is the security problem? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-04 02:06 +0000
Re: Is it possible C is the security problem? Ian Collins <ian-news@hotmail.com> - 2015-11-04 14:12 +1300
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-04 07:02 +0000
Re: Is it possible C is the security problem? Ian Collins <ian-news@hotmail.com> - 2015-11-04 20:42 +1300
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-04 08:06 +0000
Re: Is it possible C is the security problem? David Brown <david.brown@hesbynett.no> - 2015-11-04 11:25 +0100
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-04 11:49 +0000
Re: Is it possible C is the security problem? David Brown <david.brown@hesbynett.no> - 2015-11-04 13:46 +0100
Re: Is it possible C is the security problem? raltbos@xs4all.nl (Richard Bos) - 2015-11-17 21:58 +0000
Re: Is it possible C is the security problem? David Brown <david.brown@hesbynett.no> - 2015-11-17 23:37 +0100
Re: Is it possible C is the security problem? David Thompson <dave.thompson2@verizon.net> - 2015-12-06 07:55 -0500
Re: Is it possible C is the security problem? Les Cargill <lcargill99@comcast.com> - 2015-12-06 14:23 -0600
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-03 15:59 +0000
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-03 16:55 +0000
Re: Is it possible C is the security problem? see.my.homepage@gmail.com - 2015-11-04 02:29 -0800
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-04 10:48 +0000
Re: Is it possible C is the security problem? see.my.homepage@gmail.com - 2015-11-04 14:11 -0800
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-05 00:39 +0000
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-05 01:15 +0000
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-05 02:02 +0000
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-04 18:31 -0800
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-05 12:38 +0000
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-04 18:24 -0800
Re: Is it possible C is the security problem? Keith Thompson <kst-u@mib.org> - 2015-11-04 19:37 -0800
Re: Is it possible C is the security problem? David Brown <david.brown@hesbynett.no> - 2015-11-05 13:24 +0100
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-05 06:47 -0800
Re: Is it possible C is the security problem? see.my.homepage@gmail.com - 2015-11-05 00:35 -0800
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-05 09:55 +0000
Re: Is it possible C is the security problem? see.my.homepage@gmail.com - 2015-11-05 05:02 -0800
Re: Is it possible C is the security problem? raltbos@xs4all.nl (Richard Bos) - 2015-11-06 10:18 +0000
Re: Is it possible C is the security problem? see.my.homepage@gmail.com - 2015-11-06 05:57 -0800
Re: Is it possible C is the security problem? James Kuyper <jameskuyper@verizon.net> - 2015-11-04 08:32 -0500
Re: Is it possible C is the security problem? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2015-11-03 15:01 +0000
Re: Is it possible C is the security problem? Bartc <bc@freeuk.com> - 2015-11-03 15:10 +0000
Re: Is it possible C is the security problem? Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-11-03 11:02 -0500
Re: Is it possible C is the security problem? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2015-11-03 18:13 +0000
Re: Is it possible C is the security problem? Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-11-03 15:16 -0500
Re: Is it possible C is the security problem? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2015-11-04 09:38 +0000
Re: Is it possible C is the security problem? David Brown <david.brown@hesbynett.no> - 2015-11-04 11:38 +0100
Re: Is it possible C is the security problem? James Kuyper <jameskuyper@verizon.net> - 2015-11-03 11:58 -0500
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-03 09:13 -0800
Re: Is it possible C is the security problem? gazelle@shell.xmission.com (Kenny McCormack) - 2015-11-03 18:08 +0000
Re: Is it possible C is the security problem? Nobody <nobody@nowhere.invalid> - 2015-11-04 04:49 +0000
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-04 02:22 -0800
Re: Is it possible C is the security problem? gazelle@shell.xmission.com (Kenny McCormack) - 2015-11-04 13:28 +0000
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-04 08:39 -0800
Re: Is it possible C is the security problem? John Bode <jfbode1029@gmail.com> - 2015-11-03 10:45 -0800
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-03 11:05 -0800
Re: Is it possible C is the security problem? Les Cargill <lcargill99@comcast.com> - 2015-11-03 18:09 -0600
Is it possible C is the security problem? Chad <cdalten@gmail.com> - 2015-11-04 01:15 -0800
Re: Is it possible C is the security problem? gazelle@shell.xmission.com (Kenny McCormack) - 2015-11-04 13:31 +0000
Re: Is it possible C is the security problem? G G <gdotone@gmail.com> - 2015-11-18 10:55 -0800
Re: Is it possible C is the security problem? James Kuyper <jameskuyper@verizon.net> - 2015-11-18 14:05 -0500
Re: Is it possible C is the security problem? "D. Aaron Sawyer" <aaron@110.net> - 2015-11-18 19:47 -0500
Re: Is it possible C is the security problem? raltbos@xs4all.nl (Richard Bos) - 2015-11-20 10:43 +0000
Page 5 of 9 — ← Prev page 1 2 3 4 [5] 6 7 8 9 Next page →
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2015-11-20 20:06 -0800 |
| Message-ID | <bf9249f0-0a59-4e48-addd-7cb31855cce9@googlegroups.com> |
| In reply to | #76717 |
On Saturday, November 21, 2015 at 3:50:12 AM UTC, Keith Thompson wrote:
> Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
> [...]
> > In fact qsort resorts to
> > insertion sort when the sub-arrays get small.
> [...]
>
> Citation needed.
>
> Some particular implementations of qsort() may do so, but the
> standard says nothing about how qsort() sorts. A perverse conforming
> implementation could in principle implement qsort using bubblesort,
> or even bogosort.
>
http://www.opensource.apple.com/source/xnu/xnu-1456.1.26/bsd/kern/qsort.c
Here;s tghe start of the function
qsort(void *a, size_t n, size_t es, int (*cmp)(const void *, const void *))
{
char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
int d, swaptype, swap_cnt;
int r;
loop: SWAPINIT(a, es);
swap_cnt = 0;
if (n < 7) {
for (pm = (char *)a + es; pm < (char *) a + n * es; pm += es)
for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
pl -= es)
swap(pl, pl - es);
return;
}
Looks like an insertion sort to me. Only when n < 7.
[toc] | [prev] | [next] | [standalone]
| From | Keith Thompson <kst-u@mib.org> |
|---|---|
| Date | 2015-11-20 20:46 -0800 |
| Message-ID | <lnwptc7ydt.fsf@kst-u.example.com> |
| In reply to | #76718 |
Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
> On Saturday, November 21, 2015 at 3:50:12 AM UTC, Keith Thompson wrote:
>> Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
>> [...]
>> > In fact qsort resorts to
>> > insertion sort when the sub-arrays get small.
>> [...]
>>
>> Citation needed.
>>
>> Some particular implementations of qsort() may do so, but the
>> standard says nothing about how qsort() sorts. A perverse conforming
>> implementation could in principle implement qsort using bubblesort,
>> or even bogosort.
>>
> http://www.opensource.apple.com/source/xnu/xnu-1456.1.26/bsd/kern/qsort.c
That's just one implementation of qsort(). Did you mean to suggest that
qsort *as defined by the standard* resorts to insertion sort for small
sub-arrays?
--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2015-11-20 20:56 -0800 |
| Message-ID | <bbafc675-e728-40da-ae3f-3db0cea23fb8@googlegroups.com> |
| In reply to | #76724 |
On Saturday, November 21, 2015 at 4:46:45 AM UTC, Keith Thompson wrote: > Malcolm McLean <malcolm.mclean5@btinternet.com> writes: > > On Saturday, November 21, 2015 at 3:50:12 AM UTC, Keith Thompson wrote: > >> Malcolm McLean <malcolm.mclean5@btinternet.com> writes: > >> [...] > >> > In fact qsort resorts to > >> > insertion sort when the sub-arrays get small. > >> [...] > >> > >> Citation needed. > >> > >> Some particular implementations of qsort() may do so, but the > >> standard says nothing about how qsort() sorts. A perverse conforming > >> implementation could in principle implement qsort using bubblesort, > >> or even bogosort. > >> > > http://www.opensource.apple.com/source/xnu/xnu-1456.1.26/bsd/kern/qsort.c > > That's just one implementation of qsort(). Did you mean to suggest that > qsort *as defined by the standard* resorts to insertion sort for small > sub-arrays? > No, of course it may be implemented using any algorithm. The names suggests quicksort, and that appears to be the best general- purpose sort. But not for the final few steps. I'm not quite sure how the cutoff point of n <= 6 was derived, but, as I expected, the first production quality qsort implementation I looked at used insertion sort for short sub-arrays..
[toc] | [prev] | [next] | [standalone]
| From | Robert Wessel <robertwessel2@yahoo.com> |
|---|---|
| Date | 2015-11-21 04:58 -0600 |
| Message-ID | <5ai05bhj7il2436mvoes1n4lt94h7desbb@4ax.com> |
| In reply to | #76725 |
On Fri, 20 Nov 2015 20:56:25 -0800 (PST), Malcolm McLean <malcolm.mclean5@btinternet.com> wrote: >On Saturday, November 21, 2015 at 4:46:45 AM UTC, Keith Thompson wrote: >> Malcolm McLean <malcolm.mclean5@btinternet.com> writes: >> > On Saturday, November 21, 2015 at 3:50:12 AM UTC, Keith Thompson wrote: >> >> Malcolm McLean <malcolm.mclean5@btinternet.com> writes: >> >> [...] >> >> > In fact qsort resorts to >> >> > insertion sort when the sub-arrays get small. >> >> [...] >> >> >> >> Citation needed. >> >> >> >> Some particular implementations of qsort() may do so, but the >> >> standard says nothing about how qsort() sorts. A perverse conforming >> >> implementation could in principle implement qsort using bubblesort, >> >> or even bogosort. >> >> >> > http://www.opensource.apple.com/source/xnu/xnu-1456.1.26/bsd/kern/qsort.c >> >> That's just one implementation of qsort(). Did you mean to suggest that >> qsort *as defined by the standard* resorts to insertion sort for small >> sub-arrays? >> >No, of course it may be implemented using any algorithm. >The names suggests quicksort, and that appears to be the best general- >purpose sort. But not for the final few steps. I'm not quite sure >how the cutoff point of n <= 6 was derived, but, as I expected, >the first production quality qsort implementation I looked at >used insertion sort for short sub-arrays.. At least several qsorts() actually implement Musser's Introsort, and it's pretty common for C++ std:sort. Introsort is interesting here as it solves a similar problem as the one being discussed. Even the best Quicksort implementations are vulnerable to pathological input data sets that cause the runtime to go quadratic (and the most interesting* part of Musser's paper is the demonstration of just how easy it is to build pathological datasets for the common Quicksort implementations). Anyway, Introsort keeps track of how well Quicksort is partitioning things, and if it's going poorly, it switches to Heapsort for that partition, thus getting the high performance of Quicksort while retaining O(n log n) performance even on data sets that would cause Quicksort to go quadratic. For Introsort, the tracking function basically just compares the size of the partition to how big it should be ideally, and if the ratio is too large, switches to Heapsort. For example, if you think of Quicksort as a purely recursive function (not actually practical, but that's a different issue), after (say) three recursive partitioning operations, the partitions ideally should be 1/8th the size of the input dataset. If the partition is larger than some multiple of that, you Heapsort. The only real trick is picking that factor, and as a practical matter, it's not very critical (in fact, it's most commonly approximated by just tracking the depth of the recursion, and the switch occurs if the depth exceeds some multiple of lg(n)). There's definitely a parallel there to using an insertion (or bubble) sort, and switching to a Quicksort if it's performing poorly. *Not to cast aspersions on the algorithm, but it's one of those things that's utterly obvious once you've been told about it.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2015-11-21 04:59 -0800 |
| Message-ID | <4541d7c8-dd60-4603-a625-5cc80dda2ac8@googlegroups.com> |
| In reply to | #76747 |
On Saturday, November 21, 2015 at 10:58:54 AM UTC, robert...@yahoo.com wrote: > > Introsort is interesting here as it solves a similar problem as the > one being discussed. Even the best Quicksort implementations are > vulnerable to pathological input data sets that cause the runtime to > go quadratic (and the most interesting* part of Musser's paper is the > demonstration of just how easy it is to build pathological datasets > for the common Quicksort implementations). Anyway, Introsort keeps > track of how well Quicksort is partitioning things, and if it's going > poorly, it switches to Heapsort for that partition, thus getting the > high performance of Quicksort while retaining O(n log n) performance > even on data sets that would cause Quicksort to go quadratic. > > For Introsort, the tracking function basically just compares the size > of the partition to how big it should be ideally, and if the ratio is > too large, switches to Heapsort. For example, if you think of > Quicksort as a purely recursive function (not actually practical, but > that's a different issue), after (say) three recursive partitioning > operations, the partitions ideally should be 1/8th the size of the > input dataset. If the partition is larger than some multiple of that, > you Heapsort. The only real trick is picking that factor, and as a > practical matter, it's not very critical (in fact, it's most commonly > approximated by just tracking the depth of the recursion, and the > switch occurs if the depth exceeds some multiple of lg(n)). > > There's definitely a parallel there to using an insertion (or bubble) > sort, and switching to a Quicksort if it's performing poorly. > > > *Not to cast aspersions on the algorithm, but it's one of those things > that's utterly obvious once you've been told about it. > It's a question of knowing which inputs are likely. I can't open a postscript file on this whizzy 2015 Windows 10 machine, so I can't read the paper. I had thought that median of three (first, last, middle) as the pivot was pretty safe, except for contrived attack sequences, of course. But it is a question of knowing what is likely. The possibilities I can think of are 1) random data. 2) essentially unordered data but with some internal structure that deviates very much from randomness. 3) Almost sorted data with football league type swaps. 4) Almost sorted data with some items in random positions. 5) Data where large regions of keys are equal. 6) Data which is sorted except for a few new items appended. 7) Sorted data. 8) Any of the above, in reverse order. 9) Malicious attack data designed to create worst case performance. 10) Null or trivial data consisting of 0-3 [4, 5, 6, 7?] items.
[toc] | [prev] | [next] | [standalone]
| From | Robert Wessel <robertwessel2@yahoo.com> |
|---|---|
| Date | 2015-11-21 13:26 -0600 |
| Message-ID | <d1h15bteg6jnj8r1h1u0oigilbdb8re9o3@4ax.com> |
| In reply to | #76764 |
On Sat, 21 Nov 2015 04:59:24 -0800 (PST), Malcolm McLean <malcolm.mclean5@btinternet.com> wrote: >On Saturday, November 21, 2015 at 10:58:54 AM UTC, robert...@yahoo.com wrote: >> >> Introsort is interesting here as it solves a similar problem as the >> one being discussed. Even the best Quicksort implementations are >> vulnerable to pathological input data sets that cause the runtime to >> go quadratic (and the most interesting* part of Musser's paper is the >> demonstration of just how easy it is to build pathological datasets >> for the common Quicksort implementations). Anyway, Introsort keeps >> track of how well Quicksort is partitioning things, and if it's going >> poorly, it switches to Heapsort for that partition, thus getting the >> high performance of Quicksort while retaining O(n log n) performance >> even on data sets that would cause Quicksort to go quadratic. >> >> For Introsort, the tracking function basically just compares the size >> of the partition to how big it should be ideally, and if the ratio is >> too large, switches to Heapsort. For example, if you think of >> Quicksort as a purely recursive function (not actually practical, but >> that's a different issue), after (say) three recursive partitioning >> operations, the partitions ideally should be 1/8th the size of the >> input dataset. If the partition is larger than some multiple of that, >> you Heapsort. The only real trick is picking that factor, and as a >> practical matter, it's not very critical (in fact, it's most commonly >> approximated by just tracking the depth of the recursion, and the >> switch occurs if the depth exceeds some multiple of lg(n)). >> >> There's definitely a parallel there to using an insertion (or bubble) >> sort, and switching to a Quicksort if it's performing poorly. >> >> >> *Not to cast aspersions on the algorithm, but it's one of those things >> that's utterly obvious once you've been told about it. >> >It's a question of knowing which inputs are likely. >I can't open a postscript file on this whizzy 2015 Windows 10 machine, >so I can't read the paper. I had thought that median of three (first, >last, middle) as the pivot was pretty safe, except for contrived attack >sequences, of course. >But it is a question of knowing what is likely. The possibilities >I can think of are >1) random data. >2) essentially unordered data but with some internal structure that >deviates very much from randomness. >3) Almost sorted data with football league type swaps. >4) Almost sorted data with some items in random positions. >5) Data where large regions of keys are equal. >6) Data which is sorted except for a few new items appended. >7) Sorted data. >8) Any of the above, in reverse order. >9) Malicious attack data designed to create worst case performance. >10) Null or trivial data consisting of 0-3 [4, 5, 6, 7?] items. In 2015 it's fairly foolish to assume that #9 is never going to be true, at least for the general case. And it turns out to be pretty simple to generate bad inputs for median-of-three Quicksort. There are a number of free PS viewers for Windows.
[toc] | [prev] | [next] | [standalone]
| From | Eric Sosman <esosman@comcast-dot-net.invalid> |
|---|---|
| Date | 2015-11-21 14:38 -0500 |
| Message-ID | <n2qh35$o6r$1@dont-email.me> |
| In reply to | #76789 |
On 11/21/2015 2:26 PM, Robert Wessel wrote:
> On Sat, 21 Nov 2015 04:59:24 -0800 (PST), Malcolm McLean
> <malcolm.mclean5@btinternet.com> wrote:
>[...]
>> But it is a question of knowing what is likely. The possibilities
>> I can think of are
>>[...]
>> 9) Malicious attack data designed to create worst case performance.
>
> In 2015 it's fairly foolish to assume that #9 is never going to be
> true, at least for the general case. [...]
Not precisely a malicious attack on a sort implementation,
but closely related:
http://www.cs.virginia.edu/~cs216/Fall2005/notes/CrosbyWallach_UsenixSec2003.pdf
--
esosman@comcast-dot-net.invalid
"Don't be afraid of work. Make work afraid of you." -- TLM
[toc] | [prev] | [next] | [standalone]
| From | glen herrmannsfeldt <gah@ugcs.caltech.edu> |
|---|---|
| Date | 2015-11-21 06:49 +0000 |
| Message-ID | <n2p456$l69$1@speranza.aioe.org> |
| In reply to | #76718 |
Malcolm McLean <malcolm.mclean5@btinternet.com> wrote:
> On Saturday, November 21, 2015 at 3:50:12 AM UTC, Keith Thompson wrote:
(snip on insertion sort and quick sort)
>> Some particular implementations of qsort() may do so, but the
>> standard says nothing about how qsort() sorts. A perverse conforming
>> implementation could in principle implement qsort using bubblesort,
>> or even bogosort.
> http://www.opensource.apple.com/source/xnu/xnu-1456.1.26/bsd/kern/qsort.c
(snip)
> loop: SWAPINIT(a, es);
> swap_cnt = 0;
> if (n < 7) {
> for (pm = (char *)a + es; pm < (char *) a + n * es; pm += es)
> for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
> pl -= es)
> swap(pl, pl - es);
> return;
> }
> Looks like an insertion sort to me. Only when n < 7.
The one I have seen described just returns when n<7, and then does
an insertion sort over the whole array after all the quicksort
recursions are done. This way, the overhead, small as it is, is
only done once.
-- glen
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2015-11-20 22:56 -0800 |
| Message-ID | <3b08829b-f0bd-4fa5-bd29-b2d2a77af3b5@googlegroups.com> |
| In reply to | #76731 |
On Saturday, November 21, 2015 at 6:49:25 AM UTC, glen herrmannsfeldt wrote: > Malcolm McLean <malcolm.mclean5@btinternet.com> wrote: > > The one I have seen described just returns when n<7, and then does > an insertion sort over the whole array after all the quicksort > recursions are done. This way, the overhead, small as it is, is > only done once. > That's a good idea. Certainly the qsorts which ship with compilers these days tend to be very fast. One I tested made about a third as many calls to the comparison as a simple but not naive quicksort I coded myself.
[toc] | [prev] | [next] | [standalone]
| From | Robert Wessel <robertwessel2@yahoo.com> |
|---|---|
| Date | 2015-11-21 04:36 -0600 |
| Message-ID | <i4i05b1o1r6srsn5rgoesbsll814rf787j@4ax.com> |
| In reply to | #76731 |
On Sat, 21 Nov 2015 06:49:11 +0000 (UTC), glen herrmannsfeldt
<gah@ugcs.caltech.edu> wrote:
>Malcolm McLean <malcolm.mclean5@btinternet.com> wrote:
>> On Saturday, November 21, 2015 at 3:50:12 AM UTC, Keith Thompson wrote:
>
>(snip on insertion sort and quick sort)
>
>>> Some particular implementations of qsort() may do so, but the
>>> standard says nothing about how qsort() sorts. A perverse conforming
>>> implementation could in principle implement qsort using bubblesort,
>>> or even bogosort.
>
>> http://www.opensource.apple.com/source/xnu/xnu-1456.1.26/bsd/kern/qsort.c
>
>(snip)
>
>> loop: SWAPINIT(a, es);
>> swap_cnt = 0;
>> if (n < 7) {
>> for (pm = (char *)a + es; pm < (char *) a + n * es; pm += es)
>> for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
>> pl -= es)
>> swap(pl, pl - es);
>> return;
>> }
>
>> Looks like an insertion sort to me. Only when n < 7.
>
>The one I have seen described just returns when n<7, and then does
>an insertion sort over the whole array after all the quicksort
>recursions are done. This way, the overhead, small as it is, is
>only done once.
That was the usual approach in the past. These days cache effects
usually overcome the extra overhead of sorting small partitions.
Basically when you get to a small partition, it's already in (near)
cache, so insertion sorting it is quite fast. If you wait until the
end, you end up having the run the entire data set through the cache
layers again for the insertion sort pass.
[toc] | [prev] | [next] | [standalone]
| From | glen herrmannsfeldt <gah@ugcs.caltech.edu> |
|---|---|
| Date | 2015-11-21 06:44 +0000 |
| Message-ID | <n2p3t8$ke1$2@speranza.aioe.org> |
| In reply to | #76717 |
Keith Thompson <kst-u@mib.org> wrote: > Malcolm McLean <malcolm.mclean5@btinternet.com> writes: > [...] >> In fact qsort resorts to >> insertion sort when the sub-arrays get small. > [...] > Citation needed. Quicksort is often described that way in theory, and I presume that there are some implemented that way. > Some particular implementations of qsort() may do so, but the > standard says nothing about how qsort() sorts. A perverse conforming > implementation could in principle implement qsort using bubblesort, > or even bogosort. Yes, just because it is called qsort() doesn't mean that it implements quicksort. -- glen
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2015-11-21 15:59 +0000 |
| Message-ID | <8737vzny29.fsf@bsb.me.uk> |
| In reply to | #76730 |
glen herrmannsfeldt <gah@ugcs.caltech.edu> writes: > Keith Thompson <kst-u@mib.org> wrote: >> Malcolm McLean <malcolm.mclean5@btinternet.com> writes: >> [...] >>> In fact qsort resorts to >>> insertion sort when the sub-arrays get small. >> [...] > >> Citation needed. > > Quicksort is often described that way in theory, and I presume > that there are some implemented that way. Given s/Quicksort/qsort/ then yes. If quicksort is described that way, then I'd say it's a confusing misnomer. Quicksort is a particular algorithm, so a version that ducks out for small arrays is not really quicksort. It's certainly a very common thing to do, but that makes the sort another of the very many adaptive sorts that people use in real systems. <snip> -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | glen herrmannsfeldt <gah@ugcs.caltech.edu> |
|---|---|
| Date | 2015-11-21 18:33 +0000 |
| Message-ID | <n2qdea$fe1$1@speranza.aioe.org> |
| In reply to | #76777 |
Ben Bacarisse <ben.usenet@bsb.me.uk> wrote: (snip on quicksort that uses a different method on small subarrays) (then I wrote) >> Quicksort is often described that way in theory, and I presume >> that there are some implemented that way. > Given s/Quicksort/qsort/ then yes. > If quicksort is described that way, then I'd say it's a confusing > misnomer. Quicksort is a particular algorithm, so a version that ducks > out for small arrays is not really quicksort. It's certainly a very > common thing to do, but that makes the sort another of the very many > adaptive sorts that people use in real systems. I think I would call quicksort (maybe with small q) a category of related algorithms. For a similar question, consider the FFT. The important (fast) part of the Fast Fourier Transform is the process of transforming subarrays, converting an O(n**2) algorithm into O(n log n). (Interestingly similar to quicksort.) But there are many different ways to actually implement an FFT. At some point, you separate an algorithm from its implementation. But okay, the original quicksort didn't specify using insertion sort on small subarrays. Does a different pivot choice make it not quicksort? https://en.wikipedia.org/wiki/Quicksort seems to consider variants, schemes, and implementation details. -- glen
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2015-11-21 19:19 +0000 |
| Message-ID | <87mvu7ma8d.fsf@bsb.me.uk> |
| In reply to | #76787 |
glen herrmannsfeldt <gah@ugcs.caltech.edu> writes: > Ben Bacarisse <ben.usenet@bsb.me.uk> wrote: > > (snip on quicksort that uses a different method on small subarrays) > (then I wrote) > >>> Quicksort is often described that way in theory, and I presume >>> that there are some implemented that way. > >> Given s/Quicksort/qsort/ then yes. > >> If quicksort is described that way, then I'd say it's a confusing >> misnomer. Quicksort is a particular algorithm, so a version that ducks >> out for small arrays is not really quicksort. It's certainly a very >> common thing to do, but that makes the sort another of the very many >> adaptive sorts that people use in real systems. > > I think I would call quicksort (maybe with small q) a category > of related algorithms. OK. I prefer not to, but it's not a big deal. > For a similar question, consider the FFT. The important (fast) > part of the Fast Fourier Transform is the process of transforming > subarrays, converting an O(n**2) algorithm into O(n log n). > (Interestingly similar to quicksort.) But there are many different > ways to actually implement an FFT. I think that's different. FFT is the name of a family of algorithms, even if they all share some common ideas. The Wikipedia page starts "A fast Fourier transform (FFT) algorithm computes..." and then goes on to describe various named algorithms. > At some point, you separate an algorithm from its implementation. Very true, or at least separating them is very hard. But there can be essential traits shared by all implementations of an algorithm that make it what it is. > But okay, the original quicksort didn't specify using insertion > sort on small subarrays. Does a different pivot choice make it > not quicksort? As far as I'm concerned, no, but I accept there could be a debate about that. The essential pattern of partitioning and merging is what makes it quicksort, for me. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Robert Wessel <robertwessel2@yahoo.com> |
|---|---|
| Date | 2015-11-21 13:33 -0600 |
| Message-ID | <0gh15bt70pa8umbctsiaal33oouk55os4c@4ax.com> |
| In reply to | #76787 |
On Sat, 21 Nov 2015 18:33:46 +0000 (UTC), glen herrmannsfeldt <gah@ugcs.caltech.edu> wrote: >Ben Bacarisse <ben.usenet@bsb.me.uk> wrote: > >(snip on quicksort that uses a different method on small subarrays) >(then I wrote) > >>> Quicksort is often described that way in theory, and I presume >>> that there are some implemented that way. > >> Given s/Quicksort/qsort/ then yes. > >> If quicksort is described that way, then I'd say it's a confusing >> misnomer. Quicksort is a particular algorithm, so a version that ducks >> out for small arrays is not really quicksort. It's certainly a very >> common thing to do, but that makes the sort another of the very many >> adaptive sorts that people use in real systems. > >I think I would call quicksort (maybe with small q) a category >of related algorithms. > >For a similar question, consider the FFT. The important (fast) >part of the Fast Fourier Transform is the process of transforming >subarrays, converting an O(n**2) algorithm into O(n log n). >(Interestingly similar to quicksort.) But there are many different >ways to actually implement an FFT. > >At some point, you separate an algorithm from its implementation. > >But okay, the original quicksort didn't specify using insertion >sort on small subarrays. Does a different pivot choice make it >not quicksort? > >https://en.wikipedia.org/wiki/Quicksort > >seems to consider variants, schemes, and implementation details. IIRC, Hoare's original paper suggested three enhancements to the base Quicksort. Using a random pivot, using the median-of-three pivot, and using an insertion sort to finish up. So all of those are pretty much as old as Quicksort itself.
[toc] | [prev] | [next] | [standalone]
| From | glen herrmannsfeldt <gah@ugcs.caltech.edu> |
|---|---|
| Date | 2015-11-22 14:42 +0000 |
| Message-ID | <n2sk7u$10d$1@speranza.aioe.org> |
| In reply to | #76790 |
Robert Wessel <robertwessel2@yahoo.com> wrote: (snip on quicksort and varitions of it not being quicksort) (then I wrote) >>I think I would call quicksort (maybe with small q) a category >>of related algorithms. (snip) >>https://en.wikipedia.org/wiki/Quicksort >>seems to consider variants, schemes, and implementation details. > IIRC, Hoare's original paper suggested three enhancements to the base > Quicksort. Using a random pivot, using the median-of-three pivot, and > using an insertion sort to finish up. So all of those are pretty much > as old as Quicksort itself. I originally learned it from Knuth vol. 3. I probably have it not so far away, and thought I remembered those being described, but didn't look it up. I bought Knuth 2 and 3 when taking a CS class some years ago. (Before the second edition of any came out.) -- glen
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <txr@alumni.caltech.edu> |
|---|---|
| Date | 2015-11-22 14:17 -0800 |
| Message-ID | <kfnoael65n2.fsf@x-alumni2.alumni.caltech.edu> |
| In reply to | #76710 |
Malcolm McLean <malcolm.mclean5@btinternet.com> writes: > [...] > > Then as Tim says, the first optimisation everyone makes to > bubble sort is to turn it into bubble and brick sort. [...] I said no such thing. Nor would I have, since I don't think it's true.
[toc] | [prev] | [next] | [standalone]
| From | Ian Collins <ian-news@hotmail.com> |
|---|---|
| Date | 2015-11-20 14:51 +1300 |
| Message-ID | <db7clbFjpqnU4@mid.individual.net> |
| In reply to | #76559 |
Malcolm McLean wrote:
<snip>
>
> void bubblesort(unsigned char *base, int N, int width,
> int (*compfunc)(const void *e1, const void *e2))
> {
> int flag = 1;
> int i;
>
> int limit = (int) ceil(log(N) / log(2));
>
> while (flag && limit)
> {
> flag = 0;
> for (i = 0; i < N - 1;i++)
> if ((*compfunc)(base + i * width, base + (i + 1)*width) > 0)
> {
> swap(base + i * width, base + (i + 1)*width, width);
> flag = 1;
> }
> limit--;
> }
> if (flag)
> qsort(base, N, width, compfunc);
Why to you fall back to qsort here?
--
Ian Collins
[toc] | [prev] | [next] | [standalone]
| From | Robert Wessel <robertwessel2@yahoo.com> |
|---|---|
| Date | 2015-11-19 08:06 -0600 |
| Message-ID | <m2lr4b18nvudi11ar6jc52tll0vloh29uf@4ax.com> |
| In reply to | #76482 |
On Wed, 18 Nov 2015 20:38:35 -0800 (PST), Malcolm McLean <malcolm.mclean5@btinternet.com> wrote: >On Wednesday, November 18, 2015 at 9:35:19 PM UTC, Ben Bacarisse wrote: >> Malcolm McLean <malcolm.mclean5@btinternet.com> writes: >> >> > By that, I mean that all the teams have several points >> > (it only works halfway through the league). As they play >> > games, obviously a team can gain three points, or one point, >> > or no points, and can overtake rivals. >> > But it's very unlikely that a team will move more than one >> > or two places as the result of any one match. >> > You get that sort of dataset quite a bit in real life. >> >> Why not use insertion sort? Bubble sort is not the only simple >> algorithm to be good on partially sorted data, and I don't >> think it is ever the best. Do you think otherwise? If so, >> can you show some data? >> >Bubble sort can terminate after a few passes if the data >still isn't sorted. So if we've got a football league type >dataset, with occasional shuffling catastrophes, we can >resort to quicksort if our assumption that the data is >nearly sorted is wrong. >I haven't done any tests however. You can do the same with insertion sort. Just set a threshold for the number of swaps performed. And if you set the threshold at something proportional to n*log(n), the whole sort retains that big-O. Shell sort also adapts fairly well to almost sorted data, and while not as fast as (say) heapsort or quicksort, implementing just Shell sort would certainly be easier than implementing bubble/insertion plus a better sort. Of course if you already have a good sort implementation available, that changes that equation.
[toc] | [prev] | [next] | [standalone]
| From | Robert Wessel <robertwessel2@yahoo.com> |
|---|---|
| Date | 2015-11-18 15:40 -0600 |
| Message-ID | <eprp4bdoh7h5pgo20aq2k0oci0ohdvhju7@4ax.com> |
| In reply to | #76420 |
On Wed, 18 Nov 2015 09:00:23 -0800, Keith Thompson <kst-u@mib.org> wrote: >Robert Wessel <robertwessel2@yahoo.com> writes: >[...] >> Bubble sort is good on almost sorted lists only when none of the out >> of place items have to move a long way towards the front of the list >> (assuming the sort starts at the front end). So: >> >> 9 1 2 3 4 5 6 7 8 >> >> is fine, the 9 will be moved to the end in the first pass. But: >> >> 2 3 4 5 6 7 8 9 1 >> >> is horrible, since each pass can only move the 1 back a single >> position. > >There's a variant of bubble sort that reverses direction on each pass. >(Shuttle sort?) It should deal well with that kind of data. > >But of course the worst case is still pretty bad. > >[...] I've usually heard it called cocktail [shaker] sort. And yes, it improves bubble sort a bit, but insertion sort still generally (always?) has better performance. And it's a fair increase in complexity over bubble sort, which is already more complex than insertion sort.
[toc] | [prev] | [next] | [standalone]
Page 5 of 9 — ← Prev page 1 2 3 4 [5] 6 7 8 9 Next page →
Back to top | Article view | comp.lang.c
csiph-web