Re: A little help with Quicksort

["chris.danx" <chris.danx@ntlworld.com>]

"Mond" <mrsmond@hotmail.com> wrote in message
news:1408ce1d.0201011425.29c12c97@posting.google.com...
> Hi,

Hi,

> i'm having a little trouble implementing Quicksort with a doubley
> linked list and was hoping someone could put me in the right direction
> ;)

Sure.  I'll try but I can't give you much help because I am doing a very
similar exercise for next week.


> The part marked with stars above is a wee bit confusing.
>
> Why does it swap the pivot value? Is it so that when QSort is called
> again the pivot value remains on the left hand side?

Yes.  If the pivot ended up in the righthand side then it would always be
chosen, and the QSort would never terminate or cause a stack overflow (the
pivot and all the members of the righthand side are >= pivot).


> This works with arrays but converting it into working with a linked
> list is a bit harder.

Do you undestrand the algorithm and it's solution (for arrays)?  Converting
the array solution to lists like that will not work, or at least not as
easily as it would if you take the main points (choose pivot, partition,
sort) of the algorithm and coded them.  My suggestion is to break the list
into two lists, and don't try to move the pointers about.


> PS Sorry for all the .all etc stuff - it makes it clear to me that it
> is pointers ;)

It's a matter of style, and there's nothing wrong with it.


Hope this helps,
Chris