Re: A little help with Quicksort

[mrsmond@hotmail.com (Mond)]

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? :)