Messages in this thread | | | Date | Fri, 9 Mar 2001 06:09:11 -0500 (EST) | From | James R Bruce <> | Subject | Re: quicksort for linked list |
| |
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/
| |