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/
This archive was generated by hypermail 2b29 : Thu Mar 15 2001 - 21:00:10 EST