home *** CD-ROM | disk | FTP | other *** search
/ Point Programming 1 / PPROG1.ISO / pascal / swag / sorting.swg / 0027_SORT-LL.PAS.pas < prev    next >
Encoding:
Pascal/Delphi Source File  |  1993-05-28  |  3.1 KB  |  129 lines
  1. {
  2. > I have a linked list structure that I would like to sort in one of
  3. > four different ways.  I can sort Arrays using QuickSort, etc., but have no
  4. > experience sorting linked lists.  Does anyone have any source code
  5. > (preferably) or any suggestions on how to proceed?  Any help would be
  6. > appreciated.
  7.  
  8. I got Modula-2 code I wrote about one year ago. I post an excerpt from
  9. the Implementation MODULE. It should be no problem to convert it to
  10. Pascal, since the languages are rather similar.
  11. }
  12. Procedure LISTSort(Var List     : LISTType;
  13.                        Ascending: Boolean);
  14.  
  15. Var
  16.   Last  : NodeTypePtr;
  17.   Result: LISTCompareResultType;
  18.  
  19.   Procedure TailIns(    Rec  : NodeTypePtr;
  20.                     Var First: NodeTypePtr;
  21.                     Var Last : NodeTypePtr);
  22.  
  23.   begin
  24.     if (First=NIL) then First := Rec else Last^.Next := Rec end;
  25.     Last := Rec
  26.   end TailIns;
  27.  
  28.   Procedure MergeLists(    a: NodeTypePtr;
  29.                            b: NodeTypePtr): NodeTypePtr;
  30.  
  31.   Var
  32.     First: NodeTypePtr;
  33.     Last : NodeTypePtr;
  34.     Help : NodeTypePtr;
  35.  
  36.   begin
  37.     First := NIL;
  38.     While (b#NIL) do
  39.       if (a=NIL) then
  40.         a := b; b := NIL
  41.       else
  42.         if (Classes[List^.ClassID].Cmp(b^.DataPtr,a^.DataPtr)=Result)
  43.         then
  44.           Help := a; a := a^.Next
  45.         else
  46.           Help := b; b := b^.Next
  47.         end;
  48.         Help^.Next := NIL;
  49.         TailIns(Help,First,Last)
  50.       end
  51.     end;
  52.     TailIns(a,First,Last);
  53.     RETURN(First)
  54.   end MergeLists;
  55.  
  56.   Procedure MergeSort(Var Root: NodeTypePtr;
  57.                           N   : CARDinAL): NodeTypePtr;
  58.  
  59.   Var
  60.     Help: NodeTypePtr;
  61.     a,b : NodeTypePtr;
  62.  
  63.   begin
  64.     if (Root=NIL) then
  65.       RETURN(NIL)
  66.     ELSif (N>1) then
  67.       a := MergeSort(Root,N div 2);
  68.       b := MergeSort(Root,(N+1) div 2);
  69.       RETURN(MergeLists(a,b))
  70.     else
  71.       Help := Root;
  72.       Root := Root^.Next;
  73.       Help^.Next := NIL;
  74.       RETURN(Help)
  75.     end
  76.   end MergeSort;
  77.  
  78. begin
  79.   if (List^.N<2) then RETURN end;
  80.   if (Ascending) then Result := LISTGreater else Result := LISTLess end;
  81.   List^.top^.Next := MergeSort(List^.top^.Next,List^.N);
  82.   Last := List^.top;
  83.   List^.Cursor := List^.top^.Next;
  84.   While (List^.Cursor#NIL) do
  85.     List^.Cursor^.Prev := Last;
  86.     Last := List^.Cursor;
  87.     List^.Cursor := List^.Cursor^.Next
  88.   end;
  89.   Last^.Next := List^.Bottom;
  90.   List^.Bottom^.Prev := Last;
  91.   List^.CurPos := 1;
  92.   List^.Cursor := List^.top^.Next
  93. end LISTSort;
  94.  
  95. {
  96. The basic data structure is defined as follows:
  97. }
  98.  
  99. Const
  100.   MaxClasses   = 256;
  101.  
  102. Type
  103.   NodeTypePtr = Pointer to NodeType;
  104.  
  105.   NodeType = Record
  106.     Prev   : NodeTypePtr;
  107.     Next   : NodeTypePtr;
  108.     DataPtr: ADDRESS
  109.   end;
  110.  
  111.   LISTType = Pointer to ListType;
  112.  
  113.   ListType = Record
  114.     top    : NodeTypePtr;
  115.     Bottom : NodeTypePtr;
  116.     Cursor : NodeTypePtr;
  117.     N      : CARDinAL;
  118.     CurPos : CARDinAL;
  119.     ClassID: CARDinAL
  120.   end;
  121.  
  122.   ClassType = Record
  123.     Cmp  : LISTCompareProcType;
  124.     Bytes: CARDinAL
  125.   end;
  126.  
  127. Var
  128.   Classes: Array [0..MaxClasses-1] of ClassType;
  129.