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...).
9-Mar-2001 Re: quicksort for linked list by Helge Hafting@idb.hist.n
> 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, 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.
It's quicksort as long as you do pivot/split, the array gymnastics
that most implementations do to avoid updating array elements isn't
really critical to its operation.
> 1. find out how many elements there are. (Count them if necessary)
> 2. Allocate a pointer array of this size.
> 3. fill the pointer array with pointers to list members.
> 4. quicksort the pointer array
> 5. Traverse the pointer array and set the links for each
> list member to point to next/previous element pointed
> to by the array. Now you have a sorted linked list!
I think a radix sort like the following would work better with about
the same (or less) storage, provided you're comparing ints (this is
for a kernel modification after all, right?). You just need to
determine the number of passes to cover all the bits in the numbers
you want to sort.
- Jim Bruce
#define RADIX_BITS 6
#define RADIX (1 << RADIX_BITS)
#define RADIX_MASK (RADIX - 1)
struct item *radix_sort(struct item *list,int passes)
// Sort list, largest first
{
struct item *tbl[RADIX],*p,*pn;
int slot,shift;
int i,j;
// Handle trivial cases
if(!list || !list->next) return(list);
// Initialize table
for(j=0; j<RADIX; j++) tbl[j] = NULL;
for(i=0; i<passes; i++){
// split list into buckets
shift = RADIX_BITS * i;
p = list;
while(p){
pn = p->next;
slot = ((p->key) >> shift) & RADIX_MASK;
p->next = tbl[slot];
tbl[slot] = p;
p = pn;
}
// integrate back into partially ordered list
list = NULL;
for(j=0; j<RADIX; j++){
p = tbl[j];
tbl[j] = NULL; // clear out table for next pass
while(p){
pn = p->next;
p->next = list;
list = p;
p = pn;
}
}
}
// fix prev pointers in list
list->prev = NULL;
p = list;
while(pn = p->next){
pn->prev = p;
p = pn;
}
return(list);
}
-
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:09 EST