Courses/CS 460/Fall 2005/Homework/Cynthia York/Oct 8

From CSWiki

October 8th homework solutions

Contents 1 MergeSort

[edit] MergeSort

• uses several functions and a procedure to sort a list
• I presented the Map function in class

%MergeSort - takes a list, splits it into a list of singleton lists,
%            merge pairs of lists until only one sorted sublist remains
declare Map Sort Order OrderPairs 
fun {Map Xs F}
   case Xs
   of nil then nil
   [] X|Xr then {F X}|{Map Xr F}
   end
end

fun {Order Xs Zs}
   {Browse order}
   {Browse Xs}
   Z in
   case Xs
   of nil then nil
   [] X1|nil then Xs
   [] X1|X2|nil then
      if X1.1=<X2.1 then [X1 X2]
      else [X2 X1]
      end
   [] X1|X2|Xr then
      if X1.1=<X2.1 then X1|{Order {Flatten [X2 Xr]} Z}
      else X2|{Order {Flatten [X1 Xr]} Z}
      end
   end
end

fun {OrderPairs Xs Zs}
   local Z Ws X1 X2 Xr in
      {Browse orderPairs}
      {Browse Xs}
      case Xs
      of nil then nil
      [] X1|nil then X1
      [] X1|X2|nil then
	 {Browse [X1 X2]}
	 Ws={Order [X1 X2] Zs}
	 {Browse ws}
	 {Browse Ws}
	 {Flatten Ws}
      end
   end
end

fun {Sort Xs Zs}
   local X1 X2 Xr Ws Z L in
      {Browse sort}
      {Browse Xs}
      case Xs
      of nil then nil
      [] X1|nil then X1
	 [] X1|X2|Xr then
	 {Browse [X1 X2]}
	 Ws={OrderPairs [X1 X2] Zs}|{Sort Xr Z}
	 {Browse ws}
	 {Browse Ws}
	 L={Length Ws}
	 if L>1 then
	    {Sort Ws Z}
	 else
	    Ws
	 end
      end
   end
end

local  Out Ws Z
   proc {MergeSort Xs  Zs}
      % convert list to list of singleton lists
      Ws={Map Xs fun {$ X} X|nil end}
      {Browse mergeSort}
      {Browse Ws}
      % order the list of singleton lists
      Zs={Flatten {Sort Ws Z}}
   end
   

in
   {MergeSort [e f c b d a] Out}
   {Browse out}
   {Browse Out}
end