Quicksorting a linked list

From: Alan Morgan (amorgan_at_Xenon.Stanford.EDU)
Date: 07/28/04 

Date: Wed, 28 Jul 2004 20:59:50 +0000 (UTC)

The main problem with using quicksort to sort a linked list (that I know
of) is chosing a good pivot. If you always choose the first element then
you end up with O(n^2) worst case behavior. With an array you have more
options (median of first/middle/last or random element are popular
choices). It occurred to me that you can do the same thing with linked
lists as well.

During the partition stage you will be constructing two lists - smaller
and larger. There is a well known technique for picking a random line
from a file of unknown length. You can apply this to the two partition
lists as you build them and end up with a random element from each of
them that you can use in the next stage of the sort.

If you'd prefer to do the first/middle/last median method then you can
start off with a middle pointer that points to the beginning of the
(empty) smaller and larger lists. Advance it by one node for every
two you add and it will end up pointing to the element in the middle of
the list. Lather, rinse, recurse.

Obviously for both of these you need to pick your pivot the "hard way"
for the first pass. I don't see that as being a problem.

Any comments?

Alan 

-- 
Defendit numerus

Relevant Pages

  • Panic, a strange behavior of lisp program
    ... when SORT is called with a parameter that includes some that ... No actually although CLtL ... this apparent mistake in conversion from CLtL to ANSI-CL. ... Web page that lists all such "obvious" mistakes. ...
    (comp.lang.lisp)
  • RE: Incident investigation methodologies
    ... However, what sort of reaction ... Speculation gets you nowhere. ... > malware we encounter. ... > of what makes public lists useful - you can get some ...
    (Incidents)
  • Re: Detailed explanation of how a QuickSort Works
    ... Firstly, if you consider the simple "Bubble Sort" algorithm, it works by running through the entire data set, one item at a time, comparing each item to the previous item and swapping them if they are not already in the correct order. ... by simply running through the entire list just once (and splitting it into two smaller lists) you have cut the sorting time in half. ...
    (microsoft.public.vb.general.discussion)
  • Re: Ordering Products
    ... algorithms. ... lists with constrained item transpositions. ... I think while the built in sort works as a convenience, ... Overall it's about 10 times slower than pythons built in sort for large ...
    (comp.lang.python)
  • Re: Ordering Products
    ... > Kay Schluehr wrote: ... >> It would be interesting to examine some sorting algorithms on factor ... >> lists with constrained item transpositions. ... > I think while the built in sort works as a convenience, ...
    (comp.lang.python)