home *** CD-ROM | disk | FTP | other *** search
/ POINT Software Programming / PPROG1.ISO / pascal / swag / sorting.swg / 0026_SORT-DLL.PAS.pas < prev    next >
Encoding:
Pascal/Delphi Source File  |  1993-05-28  |  3.0 KB  |  75 lines
  1. {
  2. >         Now, I gotta work on sortin' em.  I believe I can 'swap' the
  3. >         positions of the Pointers eh?
  4. >
  5. >         I can't figure out how to swap the Pointers.  Could you please
  6. >         gimme a wee bit more help?  I've just started doing sorts, and
  7. >         have only used the Bubble sort at the moment in a few Programs,
  8. >         so I'm still a little shakey on sorts.  I understand the Bubble
  9.  
  10.   Here's an *example* on how to sort a linked list. There are more
  11.   efficient ways to sort a list, but this gives you all the
  12.   essential elements in doing a sort. (note that ListPtr is a doubly
  13.   linked list)
  14. }
  15.  
  16. Procedure SortList(Var FCL:ListPtr);
  17. Var
  18.   TempAnchor, TemPtr1, TemPtr2 :ListPtr;
  19.  
  20.   Procedure MoveLink(Var Anchor, Ptr1, Ptr2 :ListPtr);
  21.   Var
  22.     TemPtr3, TemPtr4 :ListPtr;
  23.   begin
  24.     TemPtr3 := Ptr1^.Next;   { temporary Pointer preserves old
  25.                                Pointer value }
  26.     TemPtr4 := Ptr2^.Last;   { ditto }
  27.  
  28.     Ptr2^.Last := Ptr1;          { do the Pointer swap }
  29.     Ptr1^.Next := Ptr2;
  30.  
  31.     Ptr1^.Last^.Next := TemPtr3; { fixup secondary Pointers }
  32.     TemPtr3^.Last := Ptr1^.Last;
  33.     Ptr1^.Last := TemPtr4;
  34.  
  35.     if TemPtr4 <> NIL then       { if temporary Pointer is not
  36.                                    NIL, then it has to point to
  37.                                    swapped Pointer }
  38.        TemPtr4^.Next := Ptr1;
  39.  
  40.     if Ptr1^.Last = NIL then     { if swapped Pointer points to
  41.                                    preceding NIL Pointer, this
  42.                                    Pointer is the new root. }
  43.        Anchor := Ptr1;
  44.   end;
  45.  
  46. begin
  47.   TempAnchor := FCL;     { holds root of list during sort }
  48.   TemPtr2 := TempAnchor; { TemPtr2 points to current data being
  49.                            Compared }
  50.   Repeat
  51.     TemPtr1 := TemPtr2; { TemPtr1 points to the next ordered
  52.                           data }
  53.     FCL := TemPtr2;     { start FCL at root of UNSorTED list -
  54.                           sorted data precede this Pointer }
  55.     Repeat
  56.       FCL := FCL^.Next;
  57.       if FCL^.data < TemPtr1^.data then   { Compare data values }
  58.         TemPtr1 := FCL;         { if necessary, reset TemPtr1 to
  59.                                    point to the new ordered value }
  60.     Until FCL^.Next = NIL;        { keep going Until you reach the
  61.                                     end of the list. After Exit,
  62.                                     the next value in order will be
  63.                                     pointed to by TemPtr1 }
  64.     if TemPtr1<>TemPtr2 then      { if TemPtr1 changed, a value
  65.                                     was found out of order }
  66.       MoveLink(TempAnchor,TemPtr1,TemPtr2) { then swap Pointers }
  67.     else
  68.       TemPtr2 := TemPtr2^.Next;  { else advance to the next
  69.                                     Pointer in list }
  70.   Until TemPtr2^.Next = NIL;      { Until we are finished sorting
  71.                                      the list }
  72.   FCL := TempAnchor;    { changes root Pointer to new root value }
  73. end;
  74.  
  75.