From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,a4d4bd32123b67d4 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2002-01-01 16:57:29 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!colt.net!newspeer.clara.net!news.clara.net!news5-gui.server.ntli.net!ntli.net!news11-gui.server.ntli.net.POSTED!not-for-mail From: "chris.danx" Newsgroups: comp.lang.ada References: <1408ce1d.0201011425.29c12c97@posting.google.com> Subject: Re: A little help with Quicksort X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 5.50.4807.1700 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4807.1700 Message-ID: Date: Wed, 2 Jan 2002 00:53:02 -0000 NNTP-Posting-Host: 62.252.137.6 X-Complaints-To: abuse@ntlworld.com X-Trace: news11-gui.server.ntli.net 1009932744 62.252.137.6 (Wed, 02 Jan 2002 00:52:24 GMT) NNTP-Posting-Date: Wed, 02 Jan 2002 00:52:24 GMT Organization: ntlworld News Service Xref: archiver1.google.com comp.lang.ada:18427 Date: 2002-01-02T00:53:02+00:00 List-Id: "Mond" 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