w.cs.cmu.edu/~jbruce/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
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
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 b
[EMAIL PROTECTED] (Rogier Wolff) writes:
> Quicksort however is an algorithm that is recursive. This means that
> it can use unbounded amounts of stack -> This is not for the kernel.
The implementation of Quicksort for arrays demands a recursive
implementation, but for doubly-linked lists there i
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 numb
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 can
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 th
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 n
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 lis
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 elem
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 sor
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 sig
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 alg
> 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++, b
++, 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 doub
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
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 this li
17 matches
Mail list logo
