Continuing our functional journey, in this post I will first present the Java based implementation of merge sort followed by F# based implementation. Finally we will repeat the same steps for QuickSort algorithm. Java based implementation of the sorting algorithms is taken from Algorithms 4th Edition by Robert Sedgewick and Kevin Wayne.
Merge Sort
Following is the Java based implementation of MergeSort, which uses an auxiliary array for maintaining intermediate values.
// stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
// copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
// merge back to a[]
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
}
// mergesort a[lo..hi] using auxiliary array aux[lo..hi]
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid + 1, hi);
merge(a, aux, lo, mid, hi);
}
Next is the F# implementation. The F# implementation replicates exactly the same pattern and codebase as we see in the above code.
let private Merge (data: int array) (aux : int array) low mid high =
let mutable i = low
let mutable j = mid + 1
for k in low..high do aux.[k] <- data.[k]
for k in [low..high] do
data.[k] <- match k with
| _ when (i > mid) -> j <- j + 1; aux.[j - 1]
| _ when j > high -> i <- i + 1; aux.[i - 1]
| _ when aux.[j] < aux.[i] -> j <- j + 1; aux.[j - 1];
| _ -> i <- i + 1; aux.[i - 1];
let rec private Sort (data: int array) (aux : int array) low high =
match low, high with
| _,_ when high <= low -> ()
| _ ->
let mid = low + (high - low) / 2
Sort data aux low mid
Sort data aux (mid+1) high
Merge data aux low mid high
()
let MergeSort (data: int array) (aux : int array) low high =
Sort data aux low high
printfn "%A" data
Notice how pattern matching has been used instead of iterative for and while loop. General advise when programming in F# is to try and avoid for and while loop and instead try and focus on pattern matching along with recursive functions.One more thing to note in the “Merge” method is how the return value of the pattern matching expression is assigned to the “data” array index element. This highlights the power of F# wherein if-else block, pattern matching block are expressions which return values.
Quick Sort
Next lets move on to the implementation of Quicksort algorithm. First the Java based implementation.
// quicksort the subarray from a[lo] to a[hi]
private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo) return;
int j = partition(a, lo, hi);
sort(a, lo, j-1);
sort(a, j+1, hi);
}
// partition the subarray a[lo..hi] so that a[lo..j-1] <= a[j] <= a[j+1..hi]
// and return the index j.
private static int partition(Comparable[] a, int lo, int hi) {
int i = lo;
int j = hi + 1;
Comparable v = a[lo];
while (true) {
// find item on lo to swap
while (less(a[++i], v))
if (i == hi) break;
// find item on hi to swap
while (less(v, a[--j]))
if (j == lo) break; // redundant since a[lo] acts as sentinel
// check if pointers cross
if (i >= j) break;
exch(a, i, j);
}
// put partitioning item v at a[j]
exch(a, lo, j);
// now, a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
return j;
}
Unlike F#’s Mergesort algorithm, the Quicksort algorithm implementation turned out to be a bit more complicated.
let private Partition (data: int array) low high =
let mutable i = low
let mutable j = high + 1
let pivot = data.[low]
let less x y = x <= y
let exchange x y =
let temp = data.[x];
data.[x] <- data.[y];
data.[y] <- temp;
y
let rec proc_i s =
match s+1 with
| x when less data.[x] pivot && x <> high -> proc_i x;
| _ -> s+1
let rec proc_j t =
match t-1 with
| x when less pivot data.[x] && x <> low -> proc_j x;
| _ -> t-1
let rec partition_data s t =
match (proc_i s), (proc_j t) with
| x , y when x >= y -> y
| x , y -> exchange x y |> partition_data x
j <- partition_data i j
exchange low j
let rec private Sort (data: int array) low high =
match low, high with
| _ , _ when high <= low -> ()
| _ ->
let j = Partition data low high
Sort data low (j - 1)
Sort data (j + 1) high
()
let QuickSort (data: int array) low high =
Sort data low high
printfn "%A" data
The structure of the above code is very much similar to what we have in Java based implementation. Its just that I have strictly tried to avoid while & for loop. In the partition method, the proc_I & proc_j recursive methods identify the I & j index values wherein the values have to be swapped. Note how inside the Partition method, I have declared helper functions like less, exchange, proc_i , proc_j and partition_data. If you found the above implementation complicated, then I will agree with you. I am still trying to learn F# language and I am very much sure that anyone who holds a better command on the language can write the above code in much simpler manner. If you are one of them, then I request you to please leave your comments.
Thanks.