Rash thoughts about .NET, C#, F# and Dynamics NAV.

Sometimes we need a function which finds the m smallest elements in a list or array.

We can use the idea of bubble sort to maintain an sorted array of the m smallest elements so far. This idea gives us a O(m*n) algorithm which solves our problem:

let bubble array element =
  let rec bubbleStep i =
    if i < (array |> Array.length) then
      match array.[i] with
        | None -> 
           if i = array.Length - 1 || array.[i+1] <> None then
             array.[i] <- Some element
                          
           bubbleStep (i+1)
        | Some x -> 
           if element < x then
             if i = 0 then 
               array.[i] <- Some element 
             else
               array.[i-1] <- Some x
               array.[i] <- Some element
             bubbleStep (i+1)
  
  bubbleStep 0
  array    
  
let mMin seq m =
  Seq.fold bubble (Array.create m None) seq

We can easily generalize this function to compute maximum and minimum:

let bubble f array element =
  let rec bubbleStep i =
    if i < (array |> Array.length) then
      match array.[i] with
        | None -> 
           if i = array.Length - 1 || array.[i+1] <> None then
             array.[i] <- Some element
                          
           bubbleStep (i+1)
        | Some x -> 
           if f element x then
             if i = 0 then 
               array.[i] <- Some element 
             else
               array.[i-1] <- Some x
               array.[i] <- Some element
             bubbleStep (i+1)
  
  bubbleStep 0
  array    
    
let mBubble f seq m =
  Seq.fold (bubble f) (Array.create m None) seq
  
let mMin seq m = mBubble (<) seq m
let mMax seq m = mBubble (>) seq m

If we don’t want to store Option-Values we can use this simplification:

let bubble f m array element =
  let rec bubbleStep i =
    if i < (array |> Array.length) then
      let x = array.[i]
      if f element x then
         if i = 0 then 
           array.[i] <- element 
         else
           array.[i-1] <- x
           array.[i] <- element
         bubbleStep (i+1)
  
  if Array.length array < m then
    let newArray = Array.append [|element|] array 
    newArray 
      |> Array.sort 
          (fun a b -> 
            if a = b then 0 
            elif f a b then 1 else -1)
    newArray
  else
    bubbleStep 0
    array    
    
let mBubble f seq m =    
  Seq.fold (bubble f m) Array.empty seq
  
let mMin seq m = mBubble (<) seq m
let mMax seq m = mBubble (>) seq m