Date: Wed, 4 Jun 1997 22:58:53 -0400 (EDT)
From: Timothy Robb <trobb AT neutrino DOT phys DOT laurentian DOT ca>
To: "Art S. Kagel" <kagel AT ns1 DOT bloomberg DOT com>
cc: djgpp AT delorie DOT com
Subject: Re: LinkedLists
In-Reply-To: <Pine.D-G.3.91.970603091249.4194A-100000@dg1>
Message-ID: <Pine.SGI.3.91.970604225308.25744A-100000@neutrino.phys.laurentian.ca>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Precedence: bulk

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
>