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

    {
    > I have a linked list structure that I would like to sort in one of
    > four different ways.  I can sort Arrays using QuickSort, etc., but have no
    > experience sorting linked lists.  Does anyone have any source code
    > (preferably) or any suggestions on how to proceed?  Any help would be
    > appreciated.

    I got Modula-2 code I wrote about one year ago. I post an excerpt from
    the Implementation MODULE. It should be no problem to convert it to
    Pascal, since the languages are rather similar.
    }
    Procedure LISTSort(Var List     : LISTType;
                           Ascending: Boolean);

    Var
      Last  : NodeTypePtr;
      Result: LISTCompareResultType;

      Procedure TailIns(    Rec  : NodeTypePtr;
                        Var First: NodeTypePtr;
                        Var Last : NodeTypePtr);

      begin
        if (First=NIL) then First := Rec else Last^.Next := Rec end;
        Last := Rec
      end TailIns;

      Procedure MergeLists(    a: NodeTypePtr;
                               b: NodeTypePtr): NodeTypePtr;

      Var
        First: NodeTypePtr;
        Last : NodeTypePtr;
        Help : NodeTypePtr;

      begin
        First := NIL;
        While (b#NIL) do
          if (a=NIL) then
            a := b; b := NIL
          else
            if (Classes[List^.ClassID].Cmp(b^.DataPtr,a^.DataPtr)=Result)
            then
              Help := a; a := a^.Next
            else
              Help := b; b := b^.Next
            end;
            Help^.Next := NIL;
            TailIns(Help,First,Last)
          end
        end;
        TailIns(a,First,Last);
        RETURN(First)
      end MergeLists;

      Procedure MergeSort(Var Root: NodeTypePtr;
                              N   : CARDinAL): NodeTypePtr;

      Var
        Help: NodeTypePtr;
        a,b : NodeTypePtr;

      begin
        if (Root=NIL) then
          RETURN(NIL)
        ELSif (N>1) then
          a := MergeSort(Root,N div 2);
          b := MergeSort(Root,(N+1) div 2);
          RETURN(MergeLists(a,b))
        else
          Help := Root;
          Root := Root^.Next;
          Help^.Next := NIL;
          RETURN(Help)
        end
      end MergeSort;

    begin
      if (List^.N<2) then RETURN end;
      if (Ascending) then Result := LISTGreater else Result := LISTLess end;
      List^.top^.Next := MergeSort(List^.top^.Next,List^.N);
      Last := List^.top;
      List^.Cursor := List^.top^.Next;
      While (List^.Cursor#NIL) do
        List^.Cursor^.Prev := Last;
        Last := List^.Cursor;
        List^.Cursor := List^.Cursor^.Next
      end;
      Last^.Next := List^.Bottom;
      List^.Bottom^.Prev := Last;
      List^.CurPos := 1;
      List^.Cursor := List^.top^.Next
    end LISTSort;

    {
    The basic data structure is defined as follows:
    }

    Const
      MaxClasses   = 256;

    Type
      NodeTypePtr = Pointer to NodeType;

      NodeType = Record
        Prev   : NodeTypePtr;
        Next   : NodeTypePtr;
        DataPtr: ADDRESS
      end;

      LISTType = Pointer to ListType;

      ListType = Record
        top    : NodeTypePtr;
        Bottom : NodeTypePtr;
        Cursor : NodeTypePtr;
        N      : CARDinAL;
        CurPos : CARDinAL;
        ClassID: CARDinAL
      end;

      ClassType = Record
        Cmp  : LISTCompareProcType;
        Bytes: CARDinAL
      end;

    Var
      Classes: Array [0..MaxClasses-1] of ClassType;

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