On 2016-Apr-20 08:45:00 +0200, Hans Petter Selasky wrote:
>There is something which I don't understand. Why is quicksort falling
>back to insertion sort which is an O(N**2) algorithm, when there exist a
>O(log(N)*log(N)*N) algorithms, which I propose as a solution to the
>"bad" characteristics
Quoting Warren Block :
On Tue, 19 Apr 2016, Aleksander Alekseev wrote:
Why Wikipedia, specifically? There are a lot of places that describe
quicksort. How about just
Note: This implementation of qsort() is designed to avoid the
worst-case complexity of N**2 that is often seen with stand
On 04/20/16 06:01, Warren Block wrote:
On Tue, 19 Apr 2016, Aleksander Alekseev wrote:
Why Wikipedia, specifically? There are a lot of places that describe
quicksort. How about just
Note: This implementation of qsort() is designed to avoid the
worst-case complexity of N**2 that is ofte
On Tue, 19 Apr 2016, Aleksander Alekseev wrote:
Why Wikipedia, specifically? There are a lot of places that describe
quicksort. How about just
Note: This implementation of qsort() is designed to avoid the
worst-case complexity of N**2 that is often seen with standard
versions.
I wo
> Why Wikipedia, specifically? There are a lot of places that describe
> quicksort. How about just
>
>Note: This implementation of qsort() is designed to avoid the
>worst-case complexity of N**2 that is often seen with standard
>versions.
I would say that this statement is just fal
On Mon, 18 Apr 2016, Hans Petter Selasky wrote:
Hi,
Are there any objections adding the following as part of documenting our
kernel's qsort function?
Index: sys/libkern/qsort.c
===
--- sys/libkern/qsort.c (revision 298202)
+++ s
On Mon, Apr 18, 2016 at 12:13 PM, Hans Petter Selasky
wrote:
> Did anyone try to generate such a fiendish set of data, and see how
> quadratic the FreeBSD's qsort() becomes?
>
Not me, but it has been done:
http://calmerthanyouare.org/2014/06/11/algorithmic-complexity-attacks-and-libc-qsort.html
On 04/18/16 16:49, Ed Schouten wrote:
2016-04-18 15:09 GMT+02:00 Hans Petter Selasky :
On 04/18/16 14:16, Aleksander Alekseev wrote:
I suggest also add a short description of how it was achieved
(randomization?).
I think the algorithm is switching to mergesort. I'll look up the paper and
add
2016-04-18 15:09 GMT+02:00 Hans Petter Selasky :
> On 04/18/16 14:16, Aleksander Alekseev wrote:
>> I suggest also add a short description of how it was achieved
>> (randomization?).
>
> I think the algorithm is switching to mergesort. I'll look up the paper and
> add that correctly before commit.
On Mon, Apr 18, 2016 at 9:09 AM, Hans Petter Selasky wrote
> I think the algorithm is switching to mergesort. I'll look up the paper
> and add that correctly before commit.
>
No, it switches to insertion sort, assuming that it's acting on an already
sorted array. If that assumption is wrong you
On 04/18/16 14:16, Aleksander Alekseev wrote:
I suggest also add a short description of how it was achieved
(randomization?).
I think the algorithm is switching to mergesort. I'll look up the paper
and add that correctly before commit.
--HPS
___
fr
Hello.
I suggest also add a short description of how it was achieved
(randomization?).
On Mon, 18 Apr 2016 13:43:38 +0200
Hans Petter Selasky wrote:
> Hi,
>
> Are there any objections adding the following as part of documenting
> our kernel's qsort function?
>
> Index: sys/libkern/qsort.c
> =
12 matches
Mail list logo
