Mail Archives: djgpp/1997/06/04/23:01:58
I've given up on Quick Sorting my list because I will be adding one item
at a time to it and the add function will call the sort function, as a
result Insertion Sort would probably be the best method.
My next problem is binary searching through a linked list....
Anyone interested I'm trying to write a C++ to HTML conversion program. For
more information check out my web page at www.geocities.com
in /SiliconValley/Vista/7489 I have a exsisting C++ to HTML converter
which uses Rogue wave's tools++, which I don't have, with a win32 binary.
Timothy Robb
Serving humanity since 1978
On Tue, 3 Jun 1997, Art S. Kagel wrote:
> 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 -