Date: Tue, 3 Jun 1997 09:40:54 -0400 (EDT)
From: "Art S. Kagel" <kagel AT ns1 DOT bloomberg DOT com>
To: Timothy Robb <trobb AT neutrino DOT phys DOT laurentian DOT ca>
Cc: djgpp AT delorie DOT com
Subject: Re: LinkedLists
In-Reply-To: <Pine.SGI.3.91.970602142204.2912A-101000@neutrino.phys.laurentian.ca>
Message-Id: <Pine.D-G.3.91.970603091249.4194A-100000@dg1>
Mime-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Precedence: bulk

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