Mail Archives: djgpp/1997/06/03/09:42:53
On Mon, 2 Jun 1997, Timothy Robb wrote:
> I'm having a problem with the attached linked list program.
>
> The class delecaration and implementaion are in the keyword.h
> keyword.cc and I have a driver.cc to test the class out.
>
> The problem is with the sorting, in perticular the
> LinkedList::partition function which is called by
> LinkedList::quickSort.
>
The only thing that I see is that the first inner loop is noop because
left->data == start->data == pivot due to the declaration/initialization
of left and of pivot left->data and pivot are identical so the while test
always returns false on the first iteration.
LinkedList *LinkedList::partition(LinkedList *start, LinkedList *end)
{
LinkedList *left = start;
Perhaps this should be:
LinkedList *left = start->next;
[SNIP]
while( strcmp(left->data, pivot) < 0 ) strcmp returns 0 the first pass
left = left->next;
[SNIP]
}
BTW quicksort is not very efficient for linked lists unless you quicksort
an array of pointers to the elements and then walk the array afterwards
relinking the list and overhead of building the array and relinking the
list can be costly. This has the added advantage of being able to use
the library qsort function which has usually been carefully optimized.
(Your implementation initially pivots on the first element which will
exhibit worst cast behavior if the list is already sorted.)
To sort the list directly try a Shell sort or, better, the Unshuffle sort
(OK that's a plug I developed the Unshuffle and published an early
version in Computer Lanuage in Nov. 1985).
Unshuffle is the only sort algorithm expressly developed to sort linked
lists. It is most efficient when sorting data exhibiting low entropy
(partly ordered already [O(Kn)]) while being comparable to quicksort and
heapsort for random data. It is more efficient for large data items
than other sorts as it only manipulates pointers. Unshuffle shows no
pathological or 'worst case' behaviors (though the 1985 version did).
Let me know if you want a copy of Unshuffle source. I have released the
algorithm for public use for all but commercial purposes (in which case I
will negotiate a small fee).
Anyway I hope I have helped with my suggestions for your code and for
other methods of sorting lists.
Art S. Kagel, kagel AT bloomberg DOT com
- Raw text -