Date: Sat, 26 Nov 2016 11:51:31 -0800 From: Mehmet Erol Sanliturk <m.e.sanliturk@gmail.com> To: =?UTF-8?Q?Arne_Dag_Fidjest=C3=B8l?= <adf@idi.ntnu.no> Cc: Tristan Verniquet <tris_vern@hotmail.com>, Hans Petter Selasky <hps@selasky.org>, freebsd hackers <freebsd-hackers@freebsd.org> Subject: Re: qsort switching to insertsort Message-ID: <CAOgwaMtsP159jgT4Faxg2jED1sh3N-zHKZRSqQNE0Cfh1NM1eA@mail.gmail.com> In-Reply-To: <B8ECCF6B-6477-441B-87F1-0DB3B36F828E@idi.ntnu.no> 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>
next in thread | previous in thread | raw e-mail | index | archive | help
On Sat, Nov 26, 2016 at 9:14 AM, Arne Dag Fidjest=C3=B8l <adf@idi.ntnu.no> = wrote: > > > On 26 Nov 2016, at 15:35, Mehmet Erol Sanliturk <m.e.sanliturk@gmail.co= m> > wrote: > > > > In quick sort , it is necessary to check worst case and switch to anoth= er > > 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 > larger partition either by tail recursion or iteration, you will only > consume O(log n) of stack, so stack overflow needn=E2=80=99t be an issue, > regardless of the input. > > -adf Important problem is caused by almost sorted values . Myself , I am counting the sorted elements first , if they exceed a large percentage of number of all elements , then I am switching to an alternative sort , otherwise a quick 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?CAOgwaMtsP159jgT4Faxg2jED1sh3N-zHKZRSqQNE0Cfh1NM1eA>