Chapter #8 Examples in Oz

% Utility functions
proc {While Expr Stmt}
   if {Expr} then {Stmt} {While Expr Stmt} end
end

fun {ArrayMax A}
   N = {NewCell A.{Array.low A}}
in
   for I in {Array.low A}..{Array.high A} do
      if @N < A.I then
         N := A.I
      end
   end
   @N
end

fun {ListToArray L}
   N = {Length L}
   A = {NewArray 1 N _}
in
   for I in 1..N do
      A.I := {Nth L I}
   end
   A
end

% 8.2 Counting Sort
proc {CountingSort A K B}
   C = {NewArray 0 K _}
in
   % Instantiate and initialize lookup array for calculating
   % sorted positions of each element.
   B = {NewArray 1 {Array.high A} _}
   for I in 0..K do
      C.I = 0
   end

   % Count the occurrences of each number.
   for J in 1..{Array.high A} do
      C.(A.J) := C.(A.J) + 1
   end

   % For each i from 0 to k, calculate the sorted position of
   % the last element of array with a key equal to i.
   for I in 1..K do
      C.I := C.I + C.(I-1)
   end

   % Copy the elements of array to their sorted positions in sorted.
   local
      J = {NewCell {Array.high A}}
   in
      {While
         fun {$} @J >= 1 end
         proc {$}
            B.(C.(A.@J)) := A.@J
            C.(A.@J) := C.(A.@J) - 1
            J := @J - 1
         end}
   end
end

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

% 8.3 Radix Sort
% Note: The algorithm does not specify sort algorithm for each digit.
%       Using modified InsertionSort for simplicity.

% calculate the optimal radix
fun {OptimalRadix A}
   Bits = {CalculateDigits 2 {ArrayMax A}}
   Lgn = {FloatToInt {Float.log {IntToFloat {Array.high A}}} / {Float.log 2.0}}
in
   {Min Bits Lgn}
end

% Determines how many digits of a given radix are necessary.
fun {CalculateDigits Radix Max}
   I = {NewCell 0}      % number of digits
   Ri = {NewCell 1}     % radix^i
in
   {While
      fun {$} @Ri =< Max end
      proc {$}
         I := @I + 1
         Ri := @Ri * Radix
      end}
   @I
end

% Extracts ith digit in base
fun {Extract Radix D N}
   (N div {Pow Radix D-1}) mod Radix
end

proc {RadixSort A Radix Digits}
   proc {DigitInsertionSort A D}
      for J in 2..{Array.high A} do
         local
            Key = A.J
            I = {NewCell J-1}
         in
            {While
               fun {$}
                  @I > 0 andthen
                     {Extract Radix D A.@I} > {Extract Radix D Key}
               end
               proc {$}
                  A.(@I+1) := A.@I
                  I := @I - 1
               end}
            A.(@I+1) := Key
         end
      end
      skip
   end
in
   for I in 1..Digits do
      {DigitInsertionSort A I}
   end
end

local
   A = {Tuple.toArray 329#457#657#839#436#720#355}
   Radix = {OptimalRadix A}
   Digits = {CalculateDigits Radix {ArrayMax A}}
in
   {RadixSort A Radix Digits}
   {Browse 'RadixSort'#{Array.toRecord '#' A}}
end

% 8.4 Bucket Sort
% Note: The algorithm does not specify data structure or key of buckets.
%       Using native lists to simplify things.
proc {BucketSort A NumBuckets B}
   % simple hash algorithm to determine number of buckets and hash
   fun {BucketHash X} 1 + X div (1 + {ArrayMax A} div NumBuckets) end
   Buckets = {NewArray 1 NumBuckets nil}
   Result = {NewCell nil}
in
   for I in 1..{Array.high A} do
      Buckets.{BucketHash A.I} := A.I | Buckets.{BucketHash A.I}
   end
   for I in 1..NumBuckets do
      Buckets.I := {Sort Buckets.I Value.'<'}
   end
   for I in 1..NumBuckets do
      Result := {Append @Result Buckets.I}
   end
   B = {ListToArray @Result}
end

local
   A = {Tuple.toArray 329#457#657#839#436#720#355}
in
   {Browse 'BucketSort'#{Array.toRecord '#' {BucketSort A 3}}}
end