/sort.cc)
10-Mar-2001 Re: quicksort for linked list by David [EMAIL PROTECTED]
> For modern machines, I'm not sure that quicksort on a linked list is
> typically much cheaper than mergesort on a linked list. The
> majority of the potential cost is likely to be in the pointer
> chas
David Wragg wrote:
> For modern machines, I'm not sure that quicksort on a linked list is
> typically much cheaper than mergesort on a linked list.
...
> For lists that don't fit into cache, the advantages of mergesort
> should become even greater if the literature on tape an
David Wragg wrote:
For modern machines, I'm not sure that quicksort on a linked list is
typically much cheaper than mergesort on a linked list.
...
For lists that don't fit into cache, the advantages of mergesort
should become even greater if the literature on tape and disk sorts
applies
/sort.cc)
10-Mar-2001 Re: quicksort for linked list by David [EMAIL PROTECTED]
For modern machines, I'm not sure that quicksort on a linked list is
typically much cheaper than mergesort on a linked list. The
majority of the potential cost is likely to be in the pointer
chasing involved in bringing
On Sat, Mar 10, 2001 at 07:50:06PM +0100, Martin Mares wrote:
> Hello!
>
> > Well, not really in this situation, after a simple modification. It is
> > trivial to show that using "shorter interval sorted first" approach one
> > can bound an amount of an extra memory, on stack or otherwise, and
ifying quicksort to resort to a mergesort
when the recursion gets too deep.
For modern machines, I'm not sure that quicksort on a linked list is
typically much cheaper than mergesort on a linked list. The majority
of the potential cost is likely to be in the pointer chasing involved
in bringing the lists
Hello!
> Well, not really in this situation, after a simple modification. It is
> trivial to show that using "shorter interval sorted first" approach one
> can bound an amount of an extra memory, on stack or otherwise, and by a
> rather small number.
By O(log N) which is in reality a small
Oliver Xymoron <[EMAIL PROTECTED]> writes:
> On Fri, 9 Mar 2001, Rogier Wolff wrote:
>
> > Quicksort however is an algorithm that is recursive. This means that
> > it can use unbounded amounts of stack -> This is not for the kernel.
>
> It is of course bounded by the input size, but yes, it
Hello!
Well, not really in this situation, after a simple modification. It is
trivial to show that using "shorter interval sorted first" approach one
can bound an amount of an extra memory, on stack or otherwise, and by a
rather small number.
By O(log N) which is in reality a small number
sort
when the recursion gets too deep.
For modern machines, I'm not sure that quicksort on a linked list is
typically much cheaper than mergesort on a linked list. The majority
of the potential cost is likely to be in the pointer chasing involved
in bringing the lists into cache, and that will be
On Sat, Mar 10, 2001 at 07:50:06PM +0100, Martin Mares wrote:
Hello!
Well, not really in this situation, after a simple modification. It is
trivial to show that using "shorter interval sorted first" approach one
can bound an amount of an extra memory, on stack or otherwise, and by a
On Fri, Mar 09, 2001 at 12:52:22PM +0100, Rogier Wolff wrote:
>
> Quicksort however is an algorithm that is recursive. This means that
> it can use unbounded amounts of stack -> This is not for the kernel.
Well, not really in this situation, after a simple modification. It is
trivial to show
On Fri, 9 Mar 2001, Rogier Wolff wrote:
> Quicksort however is an algorithm that is recursive. This means that
> it can use unbounded amounts of stack -> This is not for the kernel.
It is of course bounded by the input size, but yes, it can use O(n)
additional memory in the worst case. There's
On Fri, 9 Mar 2001, Alan Cox wrote:
> > Quicksort works just fine on a linked list, as long as you broaden
> > your view beyond the common array-based implementations. See
> > "http://www.cs.cmu.edu/~jbruce/sort.cc" for an example, although I
> > would recommend using a radix sort for linked
On Fri, 9 Mar 2001, Helge Hafting wrote:
> Manoj Sontakke wrote:
> >
> > 1. Is quicksort on doubly linked list is implemented anywhere? I need it
> > for sk_buff queues.
>
> I cannot see how the quicksort algorithm could work on a doubly
> linked list, as it rel
On Fri, Mar 09, 2001 at 01:08:57PM +0530, Manoj Sontakke wrote:
> Hi
> Sorry, these questions do not belog here but i could not find any
> better place.
>
> 1. Is quicksort on doubly linked list is implemented anywhere? I need it
> for sk_buff queues.
I would suggest
In article <[EMAIL PROTECTED]> you write:
> Quicksort however is an algorithm that is recursive. This means that
> it can use unbounded amounts of stack -> This is not for the kernel.
Maybe a heapsort, then. It is guaranteed O(n*log n), even for worst
case, and non-recursive. Yet it implies a
Helge Hafting wrote:
> Manoj Sontakke wrote:
> >
> > Hi
> > Sorry, these questions do not belog here but i could not find any
> > better place.
> >
> > 1. Is quicksort on doubly linked list is implemented anywhere? I need it
> > for sk_buf
> Quicksort works just fine on a linked list, as long as you broaden
> your view beyond the common array-based implementations. See
> "http://www.cs.cmu.edu/~jbruce/sort.cc" for an example, although I
> would recommend using a radix sort for linked lists in most situations
> (sorry for the C++,
for the C++, but it was handy...).
9-Mar-2001 Re: quicksort for linked list by Helge [EMAIL PROTECTED]
> Manoj Sontakke wrote:
> >
> > Hi
> > Sorry, these questions do not belog here but i could not find any
> > better place.
> >
> > 1. Is quicksort on d
Manoj Sontakke wrote:
>
> Hi
> Sorry, these questions do not belog here but i could not find any
> better place.
>
> 1. Is quicksort on doubly linked list is implemented anywhere? I need it
> for sk_buff queues.
I cannot see how the quicksort algorithm could wo
Manoj Sontakke wrote:
Hi
Sorry, these questions do not belog here but i could not find any
better place.
1. Is quicksort on doubly linked list is implemented anywhere? I need it
for sk_buff queues.
I cannot see how the quicksort algorithm could work on a doubly
linked list
for the C++, but it was handy...).
9-Mar-2001 Re: quicksort for linked list by Helge [EMAIL PROTECTED]
Manoj Sontakke wrote:
Hi
Sorry, these questions do not belog here but i could not find any
better place.
1. Is quicksort on doubly linked list is implemented anywhere? I need it
f
Quicksort works just fine on a linked list, as long as you broaden
your view beyond the common array-based implementations. See
"http://www.cs.cmu.edu/~jbruce/sort.cc" for an example, although I
would recommend using a radix sort for linked lists in most situations
(sorry for the C++, but
Helge Hafting wrote:
Manoj Sontakke wrote:
Hi
Sorry, these questions do not belog here but i could not find any
better place.
1. Is quicksort on doubly linked list is implemented anywhere? I need it
for sk_buff queues.
I cannot see how the quicksort algorithm could
In article [EMAIL PROTECTED] you write:
Quicksort however is an algorithm that is recursive. This means that
it can use unbounded amounts of stack - This is not for the kernel.
Maybe a heapsort, then. It is guaranteed O(n*log n), even for worst
case, and non-recursive. Yet it implies a
On Fri, Mar 09, 2001 at 01:08:57PM +0530, Manoj Sontakke wrote:
Hi
Sorry, these questions do not belog here but i could not find any
better place.
1. Is quicksort on doubly linked list is implemented anywhere? I need it
for sk_buff queues.
I would suggest that you use merge sort
On Fri, 9 Mar 2001, Helge Hafting wrote:
Manoj Sontakke wrote:
1. Is quicksort on doubly linked list is implemented anywhere? I need it
for sk_buff queues.
I cannot see how the quicksort algorithm could work on a doubly
linked list, as it relies on being able to look
up elements
On Fri, 9 Mar 2001, Alan Cox wrote:
Quicksort works just fine on a linked list, as long as you broaden
your view beyond the common array-based implementations. See
"http://www.cs.cmu.edu/~jbruce/sort.cc" for an example, although I
would recommend using a radix sort for linked lists in
On Fri, 9 Mar 2001, Rogier Wolff wrote:
Quicksort however is an algorithm that is recursive. This means that
it can use unbounded amounts of stack - This is not for the kernel.
It is of course bounded by the input size, but yes, it can use O(n)
additional memory in the worst case. There's no
On Fri, Mar 09, 2001 at 12:52:22PM +0100, Rogier Wolff wrote:
Quicksort however is an algorithm that is recursive. This means that
it can use unbounded amounts of stack - This is not for the kernel.
Well, not really in this situation, after a simple modification. It is
trivial to show that
Hi
Sorry, these questions do not belog here but i could not find any
better place.
1. Is quicksort on doubly linked list is implemented anywhere? I need it
for sk_buff queues.
2. Is Weighted Round Robin implemented in linux anyehere?
thanks in advence.
Manoj
-
To unsubscribe from
Hi
Sorry, these questions do not belog here but i could not find any
better place.
1. Is quicksort on doubly linked list is implemented anywhere? I need it
for sk_buff queues.
2. Is Weighted Round Robin implemented in linux anyehere?
thanks in advence.
Manoj
-
To unsubscribe from
33 matches
Mail list logo
