Yan Cui
I help clients go faster for less using serverless technologies.
After a long Easter holiday filled with late night coding sessions I find myself wide awake at 2am… good job I’ve still got my pluralsight subscription and a quick look at the Algorithms and Data Structures course again at least gave me something to do to relax the mind with some back-to-school style implementation of common sorting algorithms in F#:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // in-place swap | |
| let swap i j (arr : 'a []) = | |
| let tmp = arr.[i] | |
| arr.[i] <- arr.[j] | |
| arr.[j] <- tmp | |
| // http://en.wikipedia.org/wiki/Bubble_sort | |
| let bubbleSort arr = | |
| let rec loop (arr : 'a []) = | |
| let mutable swaps = 0 | |
| for i = 0 to arr.Length - 2 do | |
| if arr.[i] > arr.[i+1] then | |
| swap i (i+1) arr | |
| swaps <- swaps + 1 | |
| if swaps > 0 then loop arr else arr | |
| loop arr | |
| // http://en.wikipedia.org/wiki/Insertion_sort | |
| let insertionSort (arr : 'a []) = | |
| for i = 1 to arr.Length - 1 do | |
| let mutable j = i | |
| while j >= 1 && arr.[j] < arr.[j-1] do | |
| swap j (j-1) arr | |
| j <- j - 1 | |
| arr | |
| // http://en.wikipedia.org/wiki/Selection_sort | |
| let selectionSort (arr : 'a []) = | |
| let rec loop n (arr : 'a []) = | |
| if n >= arr.Length - 1 then arr | |
| else | |
| let mutable x, mini = arr.[n], n | |
| for i = n+1 to arr.Length - 1 do | |
| if arr.[i] < x then | |
| x <- arr.[i] | |
| mini <- i | |
| if n <> mini then swap n (mini) arr | |
| loop (n+1) arr | |
| loop 0 arr | |
| // http://en.wikipedia.org/wiki/Merge_sort | |
| let rec mergeSort (arr : 'a []) = | |
| let split (arr : _ array) = | |
| let n = arr.Length | |
| arr.[0..n/2-1], arr.[n/2..n-1] | |
| let rec merge (l : 'a array) (r : 'a array) = | |
| let n = l.Length + r.Length | |
| let res = Array.zeroCreate<'a> n | |
| let mutable i, j = 0, 0 | |
| for k = 0 to n-1 do | |
| if i >= l.Length then res.[k] <- r.[j]; j <- j + 1 | |
| elif j >= r.Length then res.[k] <- l.[i]; i <- i + 1 | |
| elif l.[i] < r.[j] then res.[k] <- l.[i]; i <- i + 1 | |
| else res.[k] <- r.[j]; j <- j + 1 | |
| res | |
| match arr with | |
| | [||] | [| _ |] -> arr | |
| | _ -> let (x, y) = split arr | |
| merge (mergeSort x) (mergeSort y) | |
| // http://en.wikipedia.org/wiki/Quicksort | |
| let rec quickSort (arr : 'a []) = | |
| match arr with | |
| | [||] | [| _ |] -> arr | |
| | _ -> let l, (r, pivots) = Array.partition (fun n -> n < arr.[0]) arr | |
| |> (fun (l, r) -> l, r |> Array.partition (fun n -> n <> arr.[0])) | |
| Array.concat <| seq { yield (quickSort l); yield pivots; yield (quickSort r) } | |
| /// left is the index of the leftmost element of the subarray | |
| /// right is the inde of the rightmost element of the subarray | |
| /// number of elements in subarray = right - left + 1 | |
| let inline partition(arr : 'a [], left, right, pivotIdx) = | |
| let pivot = arr.[pivotIdx] | |
| swap pivotIdx right arr // move pivot to the end | |
| let mutable storeIdx = left | |
| for i = left to right - 1 do // left <= i < right | |
| if arr.[i] <= pivot then | |
| swap i storeIdx arr | |
| storeIdx <- storeIdx + 1 | |
| swap storeIdx right arr // move pivot to its final place | |
| storeIdx | |
| /// in-place version of quick sort | |
| let inline quickSortInPlace (arr : 'a []) = | |
| let rec loop (arr : 'a [], left, right) = | |
| // if the array has 2 or more items | |
| if left < right then | |
| // use the middle element, and sort the elements according to the value of the pivot | |
| // and return the new idx of the pivot | |
| let pivotIdx = (left + right) / 2 | |
| let pivotNewIdx = partition(arr, left, right, pivotIdx) | |
| // recursively sort elements either side of the new pivot | |
| loop(arr, left, pivotNewIdx - 1) | |
| loop(arr, pivotNewIdx + 1, right) | |
| loop(arr, 0, arr.Length - 1) | |
| arr |
by Whilst not the most performant implementations I’m sure, I hope at least it goes to show how easily and concisely these simple algorithms can be expressed in F#! Now back to that sleep thing…
Whenever you’re ready, here are 3 ways I can help you:
- Production-Ready Serverless: Join 20+ AWS Heroes & Community Builders and 1000+ other students in levelling up your serverless game. This is your one-stop shop for quickly levelling up your serverless skills.
- I help clients launch product ideas, improve their development processes and upskill their teams. If you’d like to work together, then let’s get in touch.
- Join my community on Discord, ask questions, and join the discussion on all things AWS and Serverless.
Nice but I think Quicksort should use in-place partition in accordance with Hoare’s explanation in his original Quicksort paper otherwise you’ve taken the “quick” out of “quicksort”.
@Jon Harrop – thanks, you’re absolutely right, I’ve gone back and added the in-place version of quick sort now as well.
For an array of 1 million elements [| 1000000..-1..1 |], the simple version fails with OutOfMemoryException after quite some time, but the in-place version takes under 3 seconds to execute on my machine. When marked with inline (final version above) the same array takes around 150ms to run – a marked improvement!
That said, the built-in Array.sort function manages to sort the same 1-million element array in around 40ms, pretty impressive :-)