Sorting algorithms/Insertion sort: Difference between revisions
Content added Content deleted
Line 1,059: | Line 1,059: | ||
=={{header|F Sharp|F#}}== |
=={{header|F Sharp|F#}}== |
||
Procedural Version |
|||
<lang fsharp> |
<lang fsharp> |
||
// This function performs an insertion sort with an array. |
// This function performs an insertion sort with an array. |
||
Line 1,074: | Line 1,075: | ||
B.[j+1] <- value |
B.[j+1] <- value |
||
B // the array B is returned |
B // the array B is returned |
||
</lang> |
|||
Functional Version |
|||
<lang fsharp> |
|||
// Inserts an element into its correct place in a sorted collection |
|||
let rec private sinsert element collection = |
|||
match element, collection with |
|||
| x, [] -> [x] |
|||
| x, y::ys when x < y -> x::y::ys |
|||
| x, y::ys -> y :: (ys |> sinsert x) |
|||
// Performs Insertion Sort |
|||
let insertionSort collection = |
|||
let rec isort acc collection = |
|||
match collection, acc with |
|||
| [], _ -> acc |
|||
| x::xs, ys -> xs |> isort (sinsert x ys) |
|||
collection |> isort [] |
|||
</lang> |
</lang> |
||