Re: A little help with Quicksort

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

"Mond" <mrsmond@hotmail.com> wrote in message
news:1408ce1d.0201021422.3ef052f6@posting.google.com...
> Hi,
>
> thanks for the help!
>
> > 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.
>
> I think i understand the algorithm, so i started from scratch again
> with good old paper and pencil drawing out the nodes and pointers.  I
> got it to work out on paper by partitioning the list into two (like
> you said), the left list containing all values less than the pivot
> (where pivot = the first value in the list) and the right list
> containing all values greater or equal to the pivot.  Then the pivot
> node is prepended to the left list and its value swapped with the last
> value in that list. Eventually the lists gets smaller and smaller
> until it is just one node.  Here the nodes should be re-built by
> joining them together until the original list is in its sorted form.
> (Phew!) ;)

That's almost right.  You add the pivot to the end of one of the unsorted
lists (the lesser than list).  What happens on pen and paper?  Does it work
ok?


> Here, (joining the nodes together again), is where i had trouble
> trying to transfer this from paper into code.  I can't work out where
> to put the code - i think its somewhere like the place that is denoted
> by the stars in the code below.  Also, i think the code to to this
> involves Prepend.

Where does it make sense to join the lists you got together?  Before you've
sorted?  After you've sorted?


> If anyone could please have a look - if you can be bothered! ;) - it
> would be greatly apreciated!!!
>
> Thanks again!
>
> Mond
>
> PS Chris, are you perhaps in Level 2 Computing Sci @ Glasgow Uni? :)

Yes.



Chris