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.
You can however quicksort the list _if_ you have room enough for an
additional data structure:
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!
Steps 1,2,3 & 5 are all O(n), better than the O(nlgn) for
quicksort.
Helge Hafting
-
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