[Back to SORTING SWAG index] [Back to Main SWAG index] [Original]

    {
    >         Now, I gotta work on sortin' em.  I believe I can 'swap' the
    >         positions of the Pointers eh?
    >
    >         I can't figure out how to swap the Pointers.  Could you please
    >         gimme a wee bit more help?  I've just started doing sorts, and
    >         have only used the Bubble sort at the moment in a few Programs,
    >         so I'm still a little shakey on sorts.  I understand the Bubble

      Here's an *example* on how to sort a linked list. There are more
      efficient ways to sort a list, but this gives you all the
      essential elements in doing a sort. (note that ListPtr is a doubly
      linked list)
    }

    Procedure SortList(Var FCL:ListPtr);
    Var
      TempAnchor, TemPtr1, TemPtr2 :ListPtr;

      Procedure MoveLink(Var Anchor, Ptr1, Ptr2 :ListPtr);
      Var
        TemPtr3, TemPtr4 :ListPtr;
      begin
        TemPtr3 := Ptr1^.Next;   { temporary Pointer preserves old
                                   Pointer value }
        TemPtr4 := Ptr2^.Last;   { ditto }

        Ptr2^.Last := Ptr1;          { do the Pointer swap }
        Ptr1^.Next := Ptr2;

        Ptr1^.Last^.Next := TemPtr3; { fixup secondary Pointers }
        TemPtr3^.Last := Ptr1^.Last;
        Ptr1^.Last := TemPtr4;

        if TemPtr4 <> NIL then       { if temporary Pointer is not
                                       NIL, then it has to point to
                                       swapped Pointer }
           TemPtr4^.Next := Ptr1;

        if Ptr1^.Last = NIL then     { if swapped Pointer points to
                                       preceding NIL Pointer, this
                                       Pointer is the new root. }
           Anchor := Ptr1;
      end;

    begin
      TempAnchor := FCL;     { holds root of list during sort }
      TemPtr2 := TempAnchor; { TemPtr2 points to current data being
                               Compared }
      Repeat
        TemPtr1 := TemPtr2; { TemPtr1 points to the next ordered
                              data }
        FCL := TemPtr2;     { start FCL at root of UNSorTED list -
                              sorted data precede this Pointer }
        Repeat
          FCL := FCL^.Next;
          if FCL^.data < TemPtr1^.data then   { Compare data values }
            TemPtr1 := FCL;         { if necessary, reset TemPtr1 to
                                       point to the new ordered value }
        Until FCL^.Next = NIL;        { keep going Until you reach the
                                        end of the list. After Exit,
                                        the next value in order will be
                                        pointed to by TemPtr1 }
        if TemPtr1<>TemPtr2 then      { if TemPtr1 changed, a value
                                        was found out of order }
          MoveLink(TempAnchor,TemPtr1,TemPtr2) { then swap Pointers }
        else
          TemPtr2 := TemPtr2^.Next;  { else advance to the next
                                        Pointer in list }
      Until TemPtr2^.Next = NIL;      { Until we are finished sorting
                                         the list }
      FCL := TempAnchor;    { changes root Pointer to new root value }
    end;

[Back to SORTING SWAG index] [Back to Main SWAG index] [Original]