0 people like it.

Insertion sort

An tail recursive implementation of insertion sort on list

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 

// insertionSort xs []
let rec insertionSort xs k =
    let rec insert x ys k =
        match ys with
        | y :: ys' ->
            if x <= y then
                (List.rev (x :: k)) @ ys
            else
                insert x ys' (y :: k)
        | [] -> List.rev (x :: k)

    match xs with
    | x :: xs' ->
        let k' = insert x k []
        insertionSort xs' k'
    | [] -> k
val insertionSort : xs:'a list -> k:'a list -> 'a list (requires comparison)
val xs : 'a list (requires comparison)
val k : 'a list (requires comparison)
val insert : ('b -> 'b list -> 'b list -> 'b list) (requires comparison)
val x : 'b (requires comparison)
val ys : 'b list (requires comparison)
val k : 'b list (requires comparison)
val y : 'b (requires comparison)
val ys' : 'b list (requires comparison)
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
    interface IReadOnlyList<'T>
    interface IReadOnlyCollection<'T>
    interface IEnumerable
    interface IEnumerable<'T>
    member GetReverseIndex : rank:int * offset:int -> int
    member GetSlice : startIndex:int option * endIndex:int option -> 'T list
    member Head : 'T
    member IsEmpty : bool
    member Item : index:int -> 'T with get
    member Length : int
    ...
val rev : list:'T list -> 'T list
val x : 'a (requires comparison)
val xs' : 'a list (requires comparison)
val k' : 'a list (requires comparison)

More information

Link:http://fssnip.net/877
Posted:2 years ago
Author:tathanhdinh
Tags: continuation passing , sorting , tail recursive

This web site is created using F# and Suave web server. It is hosted on Azure and the source code is on GitHub. Contributions are welcome!

The first version of fssnip.net has been created by @tomaspetricek back in 2010. This web site is a new, open-source and contribution-friendly version.