Date: Sun, 27 Nov 2016 04:17:02 +0000 From: Tristan Verniquet <tris_vern@hotmail.com> To: Mehmet Erol Sanliturk <m.e.sanliturk@gmail.com>, =?Windows-1252?Q?Arne_Dag_Fidjest=F8l?= <adf@idi.ntnu.no> Cc: Hans Petter Selasky <hps@selasky.org>, freebsd hackers <freebsd-hackers@freebsd.org> Subject: Re: qsort switching to insertsort Message-ID: <ME1PR01MB054602129230B98C6127F607838B0@ME1PR01MB0546.ausprd01.prod.outlook.com> In-Reply-To: <CAOgwaMtsP159jgT4Faxg2jED1sh3N-zHKZRSqQNE0Cfh1NM1eA@mail.gmail.com> References: <ME1PR01MB0546A92343D712D8439B299C83880@ME1PR01MB0546.ausprd01.prod.outlook.com> <0bfb49b0-5d24-2766-6982-b4e49b0d5e81@selasky.org> <ME1PR01MB0546D041DC160763C5D3689883880@ME1PR01MB0546.ausprd01.prod.outlook.com> <CAOgwaMvUE%2BK==OE3zkpfpXa5kBC1YT4JAUVhujxEt9PcHXgqTw@mail.gmail.com> <B8ECCF6B-6477-441B-87F1-0DB3B36F828E@idi.ntnu.no>, <CAOgwaMtsP159jgT4Faxg2jED1sh3N-zHKZRSqQNE0Cfh1NM1eA@mail.gmail.com>
next in thread | previous in thread | raw e-mail | index | archive | help
From: Mehmet Erol Sanliturk <m.e.sanliturk@gmail.com> Sent: Sunday, 27 November 2016 5:51 AM To: Arne Dag Fidjest=F8l Cc: Tristan Verniquet; Hans Petter Selasky; freebsd hackers Subject: Re: qsort switching to insertsort On Sat, Nov 26, 2016 at 9:14 AM, Arne Dag Fidjest=F8l <adf@idi.ntnu.no> wro= te: > On 26 Nov 2016, at 15:35, Mehmet Erol Sanliturk <m.e.sanliturk@gmail.com>= wrote: > > In quick sort , it is necessary to check worst case and switch to another > 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 method . I you sort the smaller partition recursively first, and then sort the large= r partition either by tail recursion or iteration, you will only consume O(= log n) of stack, so stack overflow needn=92t be an issue, regardless of the= input. -adf Important problem is caused by almost sorted values . Myself , I am countin= g the sorted elements first , if they exceed a large percentage of number o= f all elements , then I am switching to an alternative sort , otherwise a q= uick sort is used . This is for a simple application . In an operating system , more complex algorithms may be more useful . Mehmet Erol Sanliturk --- It can still trigger with completely unsorted data in the top and bottom ha= lf, as long as it chooses the middle value for the pivot. The main reason n= early sorted data is vulnerable is that it is more likely to match these co= nditions, and more likely to happen in real life situations. But this is why i don't really consider it an "edge" case, there would be a= whole class of situations (like the one we had) where it would be very lik= ely to trigger with very bad side effects. Maybe, does anyone continue to use FreeBSD qsort while being aware of this = implementation detail? Under what conditions/assurances? Does anyone use FreeBSDs qsort because of this feature? Tristan ________________________________ From: Mehmet Erol Sanliturk <m.e.sanliturk@gmail.com> Sent: Sunday, 27 November 2016 5:51:31 AM To: Arne Dag Fidjest=F8l Cc: Tristan Verniquet; Hans Petter Selasky; freebsd hackers Subject: Re: qsort switching to insertsort On Sat, Nov 26, 2016 at 9:14 AM, Arne Dag Fidjest=F8l <adf@idi.ntnu.no<mail= to:adf@idi.ntnu.no>> wrote: > On 26 Nov 2016, at 15:35, Mehmet Erol Sanliturk <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 another > 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 method . I you sort the smaller partition recursively first, and then sort the large= r partition either by tail recursion or iteration, you will only consume O(= log n) of stack, so stack overflow needn=92t be an issue, regardless of the= input. -adf Important problem is caused by almost sorted values . Myself , I am countin= g the sorted elements first , if they exceed a large percentage of number o= f all elements , then I am switching to an alternative sort , otherwise a q= uick sort is used . This is for a simple application . In an operating system , more complex algorithms may be more useful . Mehmet Erol Sanliturk
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?ME1PR01MB054602129230B98C6127F607838B0>