ada liste

--  Typen:

      type Zelle;
      type Integer_Ptr is access Zelle;
      type Zelle is record
         Inhalt  : Integer;
         Next    : Integer_Ptr;
      end record;

--  benötigte mini-procedure:

      procedure Add_Front (Anchor : in out Integer_Ptr;
                            Element : in Integer_Ptr) is
      begin
         Element.Next := Anchor;
         Anchor := Element;      
      end Add_Front;

--  die Problemprocedure:

      --  Sortiert die alte Liste, indem sie immer das groesste Element
      --  vorne an eine Neue Liste anhaengt.
      procedure Sort_List (Anchor : in  out Integer_Ptr) is
         Sort_Anch, Current, Prev, Max_Ptr, PreMax_Ptr, PostMax_Ptr : Integer_Ptr;
         Sort_Anchor : Integer_Ptr := new Zelle;
         Max         : Integer := Integer'First;
      begin
         if Anchor = null then
            raise Empty_List;
         else
            while Anchor /= null loop
               if Anchor.Next = null then
                  Add_Front (Sort_Anch, Anchor);
                  Anchor := null;
               else
                  Current := Anchor;
                  while Current.Next /= null loop
                     ----  Sucht das groesste Listenelement und merkt sich das
                     ----  Element selbst sowie das davor und das dahinter.
                     if Current.Inhalt > Max then
                        PreMax_Ptr  := Prev;
                        Max_Ptr     := Current;                 
                        PostMax_Ptr := Current.Next;
                        Max := Current.Inhalt;
                     else
                        Prev    := Current;
                        Current := Current.Next;
                     end if;
                  end loop;
                  Add_Front (Sort_Anch, Max_Ptr);
                  --  Groesstes Element wird vorne an die Sortierliste angehaengt,
                  --  und aus der alten Liste entfernt.
                  if PreMax_Ptr = null then                 
                     Anchor := PostMax_Ptr;
                  else                 
                     PreMax_Ptr.Next := PostMax_Ptr;
                  end if;
               end if;                             
            end loop;  
         end if; 
         --  Die sortierte Liste hat den Anker Sort_Anch, dieser wird von der
         --  procedure zurueckgegeben.
         Anchor := Sort_Anch;
      end Sort_List;