[gclist] Sorting a doubly linked list.
Tue, 03 Dec 1996 08:29:38 +0000
Does anyone know the best algorithm for sorting a
doubly linked list without allocating a lot more
storage. I'm only using a doubly linked list because
I need to remove items quickly.
I know qsort is bogus because it takes an explosive
amount of time with sorted data or all keys the
same and these are my most likely cases.
I'm starting to think I need to keep a heapsort
type heap but this involves keeping a parent pointer.
Bubblesort (yuchh yuchh) is starting to look good.
This is because of two added complications. One I
must run the sort in little increments and give
control back to other processes. Second those
processes may remove from but not add to my list.
Third sorted data and all keys the same are likely
to be the most typical cases.
Is there a similar email group for computer science?
I mean the kind of thing Knuth does. Does anyone have
a list of computer email groups?
Charles Fiterman Geodesic Systems
Phone 312-728-7196 4745 N. Ravenswood Suite 111
Fax 312-728-6096 Chicago Il 60015
A computer language without garbage collection
is like a city without garbage collection.