Date: Sun, 27 Nov 2016 12:38:56 +0000 From: Mitchell <mitchell@wyatt672earp.force9.co.uk> To: freebsd-hackers@freebsd.org Subject: Re: qsort switching to insertsort Message-ID: <2066156.rDbTD5n9LR@daa860> In-Reply-To: <ME1PR01MB054602129230B98C6127F607838B0@ME1PR01MB0546.ausprd01.prod.outlook.com> References: <ME1PR01MB0546A92343D712D8439B299C83880@ME1PR01MB0546.ausprd01.prod.outlook.com> <CAOgwaMtsP159jgT4Faxg2jED1sh3N-zHKZRSqQNE0Cfh1NM1eA@mail.gmail.com> <ME1PR01MB054602129230B98C6127F607838B0@ME1PR01MB0546.ausprd01.prod.outlook.com>
next in thread | previous in thread | raw e-mail | index | archive | help
In "Numerical Recipes" (Press, Teukolsky, Vetterling & Flannery) the=20= Partitioning Element chosen is the median of the First, Middle & Last. = They=20 mention other techniques too. On Sunday 27 November 2016 04:17:02 Tristan Verniquet wrote: > From: Mehmet Erol Sanliturk <m.e.sanliturk@gmail.com> > Sent: Sunday, 27 November 2016 5:51 AM > To: Arne Dag Fidjest=C3=B8l > Cc: Tristan Verniquet; Hans Petter Selasky; freebsd hackers > Subject: Re: qsort switching to insertsort >=20 >=20 >=20 > On Sat, Nov 26, 2016 at 9:14 AM, Arne Dag Fidjest=C3=B8l <adf@idi.ntn= u.no> wrote: >=20 > > On 26 Nov 2016, at 15:35, Mehmet Erol Sanliturk <m.e.sanliturk@gmai= l.com>=20 wrote: > > > > In quick sort , it is necessary to check worst case and switch to a= nother > > sort method if it is detected . > > When this is not done , end result is stack overflow , etc . , but = not > > success . > > Therefore , it is not possible to eliminate an alternative sort met= hod . >=20 > I you sort the smaller partition recursively first, and then sort the= larger=20 partition either by tail recursion or iteration, you will only consume = O(log=20 n) of stack, so stack overflow needn=E2=80=99t be an issue, regardless = of the input. >=20 > -adf >=20 >=20 >=20 > Important problem is caused by almost sorted values . Myself , I am c= ounting=20 the sorted elements first , if they exceed a large percentage of number= of all=20 elements , then I am switching to an alternative sort , otherwise a qui= ck sort=20 is used . This is for a simple application . >=20 > In an operating system , more complex algorithms may be more useful .= >=20 >=20 > Mehmet Erol Sanliturk >=20 > --- >=20 > It can still trigger with completely unsorted data in the top and bot= tom=20 half, as long as it chooses the middle value for the pivot. The main re= ason=20 nearly sorted data is vulnerable is that it is more likely to match the= se=20 conditions, and more likely to happen in real life situations. >=20 > But this is why i don't really consider it an "edge" case, there woul= d be a=20 whole class of situations (like the one we had) where it would be very = likely=20 to trigger with very bad side effects. >=20 > Maybe, does anyone continue to use FreeBSD qsort while being aware of= this=20 implementation detail? Under what conditions/assurances? >=20 > Does anyone use FreeBSDs qsort because of this feature? >=20 > Tristan > ________________________________ > From: Mehmet Erol Sanliturk <m.e.sanliturk@gmail.com> > Sent: Sunday, 27 November 2016 5:51:31 AM > To: Arne Dag Fidjest=C3=B8l > Cc: Tristan Verniquet; Hans Petter Selasky; freebsd hackers > Subject: Re: qsort switching to insertsort >=20 >=20 >=20 > On Sat, Nov 26, 2016 at 9:14 AM, Arne Dag Fidjest=C3=B8l=20 <adf@idi.ntnu.no<mailto:adf@idi.ntnu.no>> wrote: >=20 > > On 26 Nov 2016, at 15:35, Mehmet Erol Sanliturk=20 <m.e.sanliturk@gmail.com<mailto:m.e.sanliturk@gmail.com>> wrote: > > > > In quick sort , it is necessary to check worst case and switch to a= nother > > sort method if it is detected . > > When this is not done , end result is stack overflow , etc . , but = not > > success . > > Therefore , it is not possible to eliminate an alternative sort met= hod . >=20 > I you sort the smaller partition recursively first, and then sort the= larger=20 partition either by tail recursion or iteration, you will only consume = O(log=20 n) of stack, so stack overflow needn=E2=80=99t be an issue, regardless = of the input. >=20 > -adf >=20 >=20 >=20 > Important problem is caused by almost sorted values . Myself , I am c= ounting=20 the sorted elements first , if they exceed a large percentage of number= of all=20 elements , then I am switching to an alternative sort , otherwise a qui= ck sort=20 is used . This is for a simple application . >=20 > In an operating system , more complex algorithms may be more useful .= >=20 >=20 > Mehmet Erol Sanliturk >=20 >=20 >=20 > _______________________________________________ > freebsd-hackers@freebsd.org mailing list > https://lists.freebsd.org/mailman/listinfo/freebsd-hackers > To unsubscribe, send any mail to "freebsd-hackers-unsubscribe@freebsd= .org"
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?2066156.rDbTD5n9LR>