2 people like it.
Like the snippet!

Distance sort

Sort collection of items based on criteria of closest distance between consecutive items. The resulting collection first element is one of two farthest items, the end element is the second of the farthest pair. For the collection of `n` items the distance function is called n*(n-1) /2 times. The distance for pair of items is assumed to not depend on items order.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41:

let distanceSort (d: 't -> 't -> 'd when 'd: comparison) (items: #seq<'t>) =
    let arr = Array.ofSeq items

    let distancesMap =
        Map.ofList [ 
            for i in 0 .. Array.length arr - 2 do
                for j in i + 1 .. Array.length arr - 1 -> 
                    (i, j), d arr[i] arr[j] 
        ]

    let distanceByIndexes i1 i2 =
        let i1, i2 = if i1 < i2 then i1, i2 else i2, i1
        distancesMap[i1, i2]

    let farthestIndexes =
        distancesMap
        |> Map.toArray
        |> Array.maxBy (fun (_, dist) -> dist)
        |> fst

    let startIndex = farthestIndexes |> fst

    let rec loop (sorted: int ResizeArray) (index: int) (unsorted: int ResizeArray) =
        match unsorted.Count with
        | 1 -> sorted.Add unsorted[0]
        | _ ->
            sorted.Add index
            unsorted.Remove index |> ignore

            let index' =
                unsorted.ToArray()
                |> Array.minBy (distanceByIndexes index)

            loop sorted index' unsorted

    let mutable allIndexes = ResizeArray [| 0 .. Array.length arr - 1 |]
    let mutable sortedIndexes = ResizeArray()
    loop sortedIndexes startIndex allIndexes

    sortedIndexes.ToArray()
    |> Array.map (fun i -> arr[i])

val distanceSort : d:('t -> 't -> 'd) -> items:#seq<'t> -> 'b [] (requires comparison)

val d : ('t -> 't -> 'd) (requires comparison)

val items : #seq<'t>

Multiple items
val seq : sequence:seq<'T> -> seq<'T>

--------------------
type seq<'T> = System.Collections.Generic.IEnumerable<'T>

val arr : 't []

module Array

from Microsoft.FSharp.Collections

val ofSeq : source:seq<'T> -> 'T []

val distancesMap : Map<(int * int),'d> (requires comparison)

Multiple items
module Map

from Microsoft.FSharp.Collections

--------------------
type Map<'Key,'Value (requires comparison)> =
  interface IReadOnlyDictionary<'Key,'Value>
  interface IReadOnlyCollection<KeyValuePair<'Key,'Value>>
  interface IEnumerable
  interface IComparable
  interface IEnumerable<KeyValuePair<'Key,'Value>>
  interface ICollection<KeyValuePair<'Key,'Value>>
  interface IDictionary<'Key,'Value>
  new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>
  member Add : key:'Key * value:'Value -> Map<'Key,'Value>
  member ContainsKey : key:'Key -> bool
  ...

--------------------
new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>

val ofList : elements:('Key * 'T) list -> Map<'Key,'T> (requires comparison)

val i : int

val length : array:'T [] -> int

val j : int

val distanceByIndexes : ('c -> 'c -> 'e) (requires comparison)

val i1 : 'c (requires comparison)

val i2 : 'c (requires comparison)

val farthestIndexes : int * int

val toArray : table:Map<'Key,'T> -> ('Key * 'T) [] (requires comparison)

val maxBy : projection:('T -> 'U) -> array:'T [] -> 'T (requires comparison)

val dist : 'd (requires comparison)

val fst : tuple:('T1 * 'T2) -> 'T1

val startIndex : int

val loop : (ResizeArray<int> -> int -> ResizeArray<int> -> unit)

val sorted : ResizeArray<int>

Multiple items
val int : value:'T -> int (requires member op_Explicit)

--------------------
type int = int32

--------------------
type int<'Measure> = int

type ResizeArray<'T> = System.Collections.Generic.List<'T>

val index : int

val unsorted : ResizeArray<int>

property System.Collections.Generic.List.Count: int with get

System.Collections.Generic.List.Add(item: int) : unit

System.Collections.Generic.List.Remove(item: int) : bool

val ignore : value:'T -> unit

val index' : int

System.Collections.Generic.List.ToArray() : int []

val minBy : projection:('T -> 'U) -> array:'T [] -> 'T (requires comparison)

val mutable allIndexes : ResizeArray<int>

val mutable sortedIndexes : ResizeArray<int>

val map : mapping:('T -> 'U) -> array:'T [] -> 'U []

Raw view Test code New version

More information

Link:	http://fssnip.net/89C
Posted:	11 months ago
Author:	Konstantin Sh
Tags:	sorting