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,FREEMAIL_FROM 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-02 14:22:30 PST Path: archiver1.google.com!postnews1.google.com!not-for-mail From: mrsmond@hotmail.com (Mond) Newsgroups: comp.lang.ada Subject: Re: A little help with Quicksort Date: 2 Jan 2002 14:22:29 -0800 Organization: http://groups.google.com/ Message-ID: <1408ce1d.0201021422.3ef052f6@posting.google.com> References: <1408ce1d.0201011425.29c12c97@posting.google.com> NNTP-Posting-Host: 195.92.67.71 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Trace: posting.google.com 1010010149 32398 127.0.0.1 (2 Jan 2002 22:22:29 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: 2 Jan 2002 22:22:29 GMT Xref: archiver1.google.com comp.lang.ada:18463 Date: 2002-01-02T22:22:29+00:00 List-Id: 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!) ;) 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. Of course this all depends on whether the rest of the code is correct!! ;) If someone could have a look below and guide me where to put this extra code, i would be very grateful!! What i have so far is below: -- Some specifications: -------------------------------------- procedure Prepend(L : in out List_Type; p : in List_Type); -- Adds the node pointed to by p to the front of list L procedure Remove(L : in out List_Type; p : out List_Type); -- Removes first node from list L and assigns p to point to it procedure Move_From_To(L, M : in out List_Type); -- Removes the front node of list L, assumed non-empty, -- and Prepends it to the front of list M --------------------------------------------------------------- procedure QSort(L : in out List_Type; Last : out List_Type) is M, N, M_Last, Temp, Pivot : List_Type; t : Integer; begin -- If the list is not empty or has more than 1 node then -- continue if (Is_Empty(L) = False) and then (L.all.Next /= null) then -- Remove the first node from L and assign it to Pivot Remove(L, Pivot); -- Make Temp point to the new first node in L Temp := L; -- Initialise two separate Lists - M & N Make_Empty(M); Make_Empty(N); -- While we have scanned all nodes loop while Temp /= null loop -- If its less than the pivot value move it from the front -- of L to the front of M if Temp.all.Val < Pivot.all.Val then Move_From_To(L, M); -- moves the front node of L to the -- start of list M -- Point Temp back to the List L to look at the other -- values Temp := L; else -- Temp.all.Val >= Pivot.all.Val -- Move Temp from the front of L to the front of N Move_From_To(L, N); Temp := L; end if; end loop; -- Add the Pivot back onto the left list, M (values less than -- Pivot) Prepend(M, Pivot); -- Find the last node in list M M_Last := Find_Last(M); -- Swap the value of the pivot (now the front node of M) with -- the last value (M_Last) of M t := M.all.Val; M.all.Val := M_Last.all.Val; M_Last.all.Val := t; -- Find the last node of N Last := Find_Last(N); -- Now sort these two lists QSort(M, M_Last); -- ****** Should prepend go here ? ****** -- ****** Something like: Prepend(L, M) ****** QSort(N, Last); -- ****** And similar code here but for N? ****** end if; -- ****** Maybe here instead? ****** -- ****** Because here it would mean there would be only 1 node -- ****** in the list so could put something like: -- ****** Prepend(N, M); L := M; -- ****** However, this would mean only the last 2 nodes would -- ****** be re-built! end QSort; 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? :)