lkml.org 
[lkml]   [2001]   [Mar]   [9]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: quicksort for linked list
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 most situations
> > (sorry for the C++, but it was handy...).
>
> In a network environment however its not so good. Quicksort has an N^2
> worst case and the input is controlled by a potential enemy.

It's not too hard to patch that up, eg quickersort. N^2 isn't too bad for
short queues anyway especially considering the complexity of the
alternatives.

> Im dubious about anyone doing more than simple bucket sorting for packets.

Assume you mean sorting into hash buckets as opposed to "count the number
of occurrences of each type of element in a narrow range, discarding the
actual element". Most hashes are subvertible too and probably don't fair
any better than N^2.

--
"Love the dolphins," she advised him. "Write by W.A.S.T.E.."

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-03-22 13:29    [W:0.042 / U:1.200 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site