A little help with Quicksort

A little help with Quicksort

[Mond]

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
;)

I have a quicksort procedure for arrays as follows:

procedure QSort(m, n : in Integer) is
         x, t, j, k : Integer;
      begin
         -- Quicksort only if there are more than 2 elements to sort
         if (n - m) > 2 then
            -- Assign the pivot to the first element in the list
            x := List(m);

            -- Set up the markers (cursors) that scan the list
            j := m + 1;     
            k := n;
     
            -- Continue sorting while the markers don't meet          
            while j /= k loop
               if List(j) < x then
                  j := j + 1; -- increment marker1 that moves from
left to right
               elsif List(k - 1) >= x then
                  k := k - 1; -- decrement marker2 that moves from
right to left
               elsif List(j) >= x and List(k - 1) < x then
                  -- Swap j and (k-1)
                  t := List(j);
                  List(j) := List(k - 1);
                  List(k - 1) := t;
               
                  -- Increment markers 
                  j := j + 1;
                  k := k - 1;
               end if;
            end loop;

            -- Update pivot value    -- ****                    
            List(m) := List(j - 1);  -- ****
            List(j - 1) := x;        -- ****
            
            -- Sort next partitions         
            QSort(m, (j - 1));
            QSort(j, n);
         end if;
      end QSort;

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

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?

Below is as far as i have got with implementing the double linked list
version:

   procedure QSort(L      : in out List_Type;
                   Last   : out List_Type) is
      Marker1, Marker2, -- points to the limits of the sorted part of
the list
      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
         -- Assign the pivot value to be the first element
         Pivot := L;
         
         Marker1 := L.all.Next;
         Marker2 := Last;
         
         -- While L is not sorted
         while Marker1 /= Marker2 loop
            if Marker1.all.Val < Pivot.all.Val then
               Marker1 := Marker1.all.Next; -- increment Marker1
            elsif Marker2.all.Prev.all.Val >= Pivot.all.Val then
               Marker2 := Marker2.all.Prev; -- decrement Marker2
            elsif (Marker1.all.Val >= Pivot.all.Val)
and(Marker2.all.Prev.all.Val < Pivot.all.Val) then
               -- Swap the values of Marker1 and (Marker2 - 1)
               t := Marker1.all.Val;
               Marker1.all.Val := Marker2.all.Prev.all.Val;
               Marker2.all.Prev.all.Val := t;
               
               -- Update Marker1 and Marker2
               Marker1 := Marker1.all.Next;
               Marker2 := Marker2.all.Prev;
            end if;
         end loop;
         
         -- Update pivot value
         -- **** ??
         -- **** ??
         
         -- Sort next partitions
         QSort(L, Marker1.all.Prev);
         QSort(Marker1, Last);
      end if;

I think if i can understand the array part (denoted with stars) i
(hopefully) will be able to do it for the linked list.

If anyone could provide some help or pointers (sorry ;) ) i would be
most grateful.

Thanks in advance,

Mond

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

Re: A little help with Quicksort

[chris.danx]

"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

Re: A little help with Quicksort

[Ted Dennison]

In article <cRsY7.25325$Zg2.2628242@news11-gui.server.ntli.net>, chris.danx
says...
>"Mond" <mrsmond@hotmail.com> wrote in message
>news:1408ce1d.0201011425.29c12c97@posting.google.com...
>> 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.

As will I, when I get to that point in the Containers implementation. :-)

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: A little help with Quicksort

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

Re: A little help with Quicksort

[chris.danx]

"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

Re: A little help with Quicksort

[Ted Dennison]

A web page with a good discussion of Quicksort is
http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/qsort.html 

I found the Java animation even more enlightening than the text.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: A little help with Quicksort

[Craig Carey]

On Thu, 03 Jan 2002 15:42:59 GMT, Ted Dennison<dennison@telepath.com>
wrote:

>A web page with a good discussion of Quicksort is
>http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/qsort.html 
>
>

A merge sort Ada algorithm that uses tasks is shown here:

http://www.math.uni-siegen.de/ortolf/ada/adab40.jpg

It demonstrates use of tasks, and it halves the list, sorts it using
2 tasks, and then merges the 2 resulting lists.