Chapter #9 Examples in Oz

% Utility functions
fun {RandomInt Min Max}
   X = {OS.rand}
   MinOS
   MaxOS
in
   {OS.randLimits ?MinOS ?MaxOS}
   Min + X*(Max - Min) div (MaxOS - MinOS)
end

{OS.srand 0}

proc {Exchange A I J}
   X = A.I
in
   A.I := A.J
   A.J := X
end

proc {While Expr Stmt}
   if {Expr} then {Stmt} {While Expr Stmt} end
end

fun {Partition A P R}
   X = A.R
   I = {NewCell P-1}
in
   for J in P..(R-1) do
      if A.J =< X then
         I := @I + 1
         {Exchange A @I J}
      end
   end
   {Exchange A @I+1 R}
   @I + 1
end

fun {RandomizedPartition A P R}
   I = {RandomInt P R}
in
   {Exchange A R I}
   {Partition A P R}
end

% 9.1 Minimum
fun {Minimum A}
   Min = {NewCell A.1}
in
   for I in 2..{Array.high A} do
      if @Min > A.I then
         Min := A.I
      end
   end
   @Min
end

local
   A  = {Tuple.toArray 5#2#4#6#1#3}
in
   {Browse 'Minimum'#{Minimum A}}
end

% 9.2 Randomized-Select
fun {RandomizedSelect A P R I}
   if P == R then
      A.P
   else
      local
         Q = {RandomizedPartition A P R}
         K = Q - P + 1
      in
         if I == K then
            A.Q
         elseif I < K then
            {RandomizedSelect A P Q-1 I}
         else
            {RandomizedSelect A Q+1 R I-K}
         end
      end
   end
end

local
   A  = {Tuple.toArray 5#2#4#6#1#3}
in
   {Browse 'RandomizedSelect'#{RandomizedSelect A 1 {Array.high A} 1}}
end

%%% 9.3 Better worst case QuickSort
proc {BetterWorstQuickSort A P R}
   if P < R then
      local
         I = (R - P + 1) div 2
         X = {Select A P R I}
         Q = {Partition X P R}
      in
         {BetterWorstQuickSort A P Q-1}
         {BetterWorstQuickSort A Q+1 R}
      end
   end
end

fun {Select A P R I}
   N = R - P + 1        % number of elements in the subarray
in
   if N == 1 then
       A.P              % base case: return the only element
   else
      local
         % Divide the subarray into ceil(n / GROUP_SIZE) groups,
         % and find the median of each group by insertion sorting
         % the group and picking the median from the sorted list.
         GroupSize = 5    % size of each group
         Groups = (N div GroupSize) + if N mod GroupSize == 0 then 0 else 1 end
         % Create an array of medians.
         Medians = {NewArray 1 Groups _}
      in
         skip
      end

      _
   end
end