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, 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 directly as in an array.
>
> You can probably find algorithms for sorting a linked list, but
> it won't be quicksort.

Here ya go (wrote this a few years ago):

// This function is so cool.
template<class T>
void list<T>::qsort(iter l, iter r, cmpfunc *cmp, void *data)
{
if(l==r) return;

iter i(l), p(l);

for(i++; i!=r; i++)
if(cmp(*i, *l, data)<0)
i.swap(++p);

l.swap(p);
qsort(l, p, cmp, data);
qsort(++p, r, cmp, data);
}

Iters are essentially list pointers with increment operations. This is a
fairly direct adaptation of the quicksort in K&R, actually.

--
"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.088 / U:1.008 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site