Chapter #7 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 {While Expr Stmt}
   if {Expr} then {Stmt} {While Expr Stmt} end
end

proc {RepeatUntil Stmt Expr}
   {Stmt}
   if {Not {Expr}} then {RepeatUntil Stmt Expr} end
end

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

% 7.1 Quicksort
proc {QuickSort A P R}
   if P < R then
      local
         Q = {Partition A P R}
      in
         {QuickSort A P Q-1}
         {QuickSort A Q+1 R}
      end
   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
         {ArrayExchange A @I J}
      end
   end
   {ArrayExchange A @I+1 R}
   @I + 1
end

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

% 7.3 Randomized Quicksort
fun {RandomizedPartition A P R}
   I = {RandomInt P R}
in
   {ArrayExchange A R I}
   {Partition A P R}
end

proc {RandomizedQuickSort A P R}
   if P =< R then
      local
         Q = {RandomizedPartition A P R}
      in
         {RandomizedQuickSort A P Q-1}
         {RandomizedQuickSort A Q+1 R}
      end
   end
end

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

% 7.4 Hoare-Partition
fun {HoarePartition A P R}
   X = A.P
   I = {NewCell P-1}
   J = {NewCell R+1}
   Return = {NewCell false}
in
   {While
      fun {$} {Not @Return} end
      proc {$}
         {RepeatUntil
            proc {$} J := @J - 1 end
            fun {$} A.@J =< X end}
         {RepeatUntil
            proc {$} I := @I + 1 end
            fun {$} A.@I >= X end}
         if @I < @J then
            {ArrayExchange A @I @J}
         else
            Return := true
         end
      end}
   @J
end

proc {HoareQuickSort A P R}
   if P < R then
      local
         Q = {HoarePartition A P R}
      in
         {HoareQuickSort A P Q}
         {HoareQuickSort A Q+1 R}
      end
   end
end

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

% 7.4 Stooge-Sort
proc {StoogeSort A I J}
   if A.I > A.J then
      {ArrayExchange A I J}
   end
   if I + 1 >= J then
      skip
   else
      local
         K = (J - I + 1) div 3
      in
         {StoogeSort A I J-K}
         {StoogeSort A I+K J}
         {StoogeSort A I J-K}
      end
   end
end

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


% 7.4 Quicksort'
proc {QuickSort_ A P R}
   {While
      fun {$} @P < R end
      proc {$}
         Q = {Partition A @P R}
      in
         {QuickSort_ A P Q-1}
         P := Q + 1
      end}
end

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