Ch3, Ex15

declare Partition QuickSort

% Puts all elems<Pivot in L1 and others in L2 
proc {Partition Pivot L ?L1 ?L2}
   case L of nil then
      L1 = nil
      L2 = nil
   [] X|Y then Y1 in
      if X < Pivot then
         L1 = X|Y1
         {Partition Pivot Y Y1 L2}
      else
         L2 = X|Y1
         {Partition Pivot Y L1 Y1}
      end
   end
end  

local
   fun {QuickSortD L}
      case L of nil then E in E#E
      [] X|nil then E in (X|E)#E
      [] X|Y then L1 L2 S1 S2 E1 E2 E3 in
         {Partition X Y L1 L2}
         %Sort L1 and L2 and then return L1+X+L2
         S1#(X|E1) = {QuickSortD L1}
         S2#E2 = {QuickSortD L2}
         E1 = S2
         S1#E2
      end
   end
in
   fun {QuickSort L}
      S#nil = {QuickSortD L}
   in
      S
   end
end


% Test Partition 
local D1 D2 E in
   {Partition 5 [5 2 7 3 4] D1 D2}
   {Browse D1}
   {Browse D2}
end

% Test QuickSort
{Browse {QuickSort nil}}
{Browse {QuickSort [1]}}
{Browse {QuickSort [2 1]}}
{Browse {QuickSort [5 2 7]}}
{Browse {QuickSort [5 2 7 3 4]}}

%=====================================
% Partition that takes difference list and
% returns difference lists
% not used in our program though
proc {Partition N D ?D1 ?D2}
   case D of nil then E1 E2 in
      D1 = E1#E1
      D2 = E2#E2
   [] X|Y then Y1 Y2 in
      if X < N then
         D1 = (X|Y1)#Y2
         {Partition N Y Y1#Y2 D2}
      else
          D2 = (X|Y1)#Y2
          {Partition N Y D1 Y1#Y2}
      end
   end
end