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,start
X-Google-Attributes: gid103376,public
X-Google-ArrivalTime: 2002-01-01 14:25:23 PST
Path: archiver1.google.com!postnews1.google.com!not-for-mail
From: mrsmond@hotmail.com (Mond)
Newsgroups: comp.lang.ada
Subject: A little help with Quicksort
Date: 1 Jan 2002 14:25:22 -0800
Organization: http://groups.google.com/
Message-ID: <1408ce1d.0201011425.29c12c97@posting.google.com>
NNTP-Posting-Host: 195.92.194.12
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Trace: posting.google.com 1009923923 1830 127.0.0.1 (1 Jan 2002 22:25:23
 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: 1 Jan 2002 22:25:23 GMT
Xref: archiver1.google.com comp.lang.ada:18421
Date: 2002-01-01T22:25:23+00:00
List-Id: <comp.lang.ada>

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