In this blog post, I will provide F# implementation for Selection & Insertion sorting algorithms. First the C#/Java based implementation of these algorithms taken from Algorithms 4th Edition by Robert Sedgewick & Kevin Wayne.
public static void selection_sort(Comparable[] a) {
int N = a.length;
for (int i = 0; i < N; i++) {
int min = i;
for (int j = i+1; j < N; j++) {
if (less(a[j], a[min])) min = j;
}
exch(a, i, min);
}
}
public static void insertion_sort(Comparable[] a) {
int N = a.length;
for (int i = 0; i < N; i++) {
for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
exch(a, j, j-1);
}
}
}
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
private static void exch(Object[] a, int i, int j) {
Object swap = a[i];
a[i] = a[j];
a[j] = swap;
}
F# implementation of these iterative algorithms is very much similar. I haven’t made use of any functional construct like pattern matching etc. instead I have tried to keep the implementation very much similar to what is present above. F# implementation of these algorithms is present below:
let SelectionSort (data: int array) =
let N = data.GetLength(0)
for i in [0..N-1] do
let mutable min = i
for j in [i+1..N-1] do
min <- if data.[j] < data.[min] then j else min
let temp = data.[i]
data.[i] <- data.[min]
data.[min] <- temp
data
let InsertionSort (data:int array) =
let N = data.GetLength(0)
for i in [1..N-1] do
for j = i downto 1 do
if data.[j] < data.[j - 1] then
let temp = data.[j]
data.[j] <- data.[j - 1]
data.[j - 1] <- temp
data
let data = [|2;20;1;11;3;5;7|]
let result = InsertionSort data
printfn "%A" result