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

## Monday, 9. February 2009

### Finding the m smallest elements in a collection in F#

Filed under: English posts,F#,Informatik — Steffen Forkmann at 11:56 Uhr

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```
Tags:

No comments yet.

#### Leave a comment

XHTML ( You can use these tags): <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> .