Re: quicksort for linked list

From: Oliver Xymoron (oxymoron@waste.org)
Date: Fri Mar 09 2001 - 13:23:54 EST


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