3 people like it.

Natural Sort Order

Sort strings as file managers usually do, treating numeric substrings as numbers.

  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: 
 42: 
 43: 
 44: 
 45: 
 46: 
 47: 
 48: 
 49: 
 50: 
 51: 
 52: 
 53: 
 54: 
 55: 
 56: 
 57: 
 58: 
 59: 
 60: 
 61: 
 62: 
 63: 
 64: 
 65: 
 66: 
 67: 
 68: 
 69: 
 70: 
 71: 
 72: 
 73: 
 74: 
 75: 
 76: 
 77: 
 78: 
 79: 
 80: 
 81: 
 82: 
 83: 
 84: 
 85: 
 86: 
 87: 
 88: 
 89: 
 90: 
 91: 
 92: 
 93: 
 94: 
 95: 
 96: 
 97: 
 98: 
 99: 
100: 
101: 
102: 
103: 
104: 
105: 
106: 
107: 
108: 
109: 
110: 
111: 
112: 
113: 
114: 
115: 
116: 
117: 
118: 
119: 
120: 
121: 
122: 
123: 
124: 
125: 
126: 
127: 
128: 
129: 
130: 
131: 

open System
open System.Text.RegularExpressions

module NaturalOrder =
    module private Impl =
        let regex = Regex ("([0-9]+)", RegexOptions.Compiled)

        let trimLeadingZeros (s: string) =
            s.TrimStart '0'

        let toChars (s: string) =
            s.ToCharArray()

        let split text =
            text
            |> regex.Split
            |> Seq.filter (fun s -> s.Length > 0)
            |> Seq.toArray

        let compareStrings (s1: string) (s2: string) =
            // each string is either all letters or all numbers
            let isNumeric1 = Char.IsDigit s1.[0]
            let isNumeric2 = Char.IsDigit s2.[0]

            // If we have a string and a number, the number comes first. When we have 
            // two strings, compare them normally. The tricky case is two numbers.
            match isNumeric1, isNumeric2 with
            | true, false -> -1
            | false, true -> 1
            | false, false -> String.Compare (s1, s2, true)
            | true, true -> 
                // leading zeros will trip us up, get rid of them
                let n1, n2 = trimLeadingZeros s1, trimLeadingZeros s2
                if n1.Length < n2.Length then -1
                elif n2.Length < n1.Length then 1
                else
                    // compare digit-by-digit
                    let chars1, chars2 = toChars n1, toChars n2
                    let result =
                        chars2
                        |> Seq.zip chars1
                        |> Seq.tryPick (fun (c1, c2) -> 
                            if c1 < c2 then Some -1
                            elif c2 < c1 then Some 1
                            else None)
                    match result with
                    | Some i -> i
                    | None -> 0

        type Pair = {
            Name: string
            Pieces: string[]
        }
    
    open Impl

    /// Sort a sequence of strings in natural order.
    let sort names =
        names
        |> Seq.map (fun name -> { Name = name; Pieces = split name })
        |> Seq.sortWith (fun p1 p2 -> Array.compareWith compareStrings p1.Pieces p2.Pieces)
        |> Seq.map (fun pair -> pair.Name)

let files = 
    [
        "VisualStudio.150x150.contrast-black_scale-100.png"
        "VisualStudio.150x150.contrast-black_scale-140.png"
        "VisualStudio.150x150.contrast-black_scale-180.png"
        "VisualStudio.150x150.contrast-black_scale-80.png"
        "Blend.150x150.contrast-black_scale-100.png"
        "Blend.150x150.contrast-black_scale-140.png"
        "Blend.150x150.contrast-black_scale-180.png"
        "Blend.150x150.contrast-black_scale-80.png"
        "Blend.70x70.contrast-black_scale-100.png"
        "Blend.70x70.contrast-black_scale-140.png"
        "Blend.70x70.contrast-black_scale-180.png"
        "Blend.70x70.contrast-black_scale-80.png"
        "VisualStudio.70x70.contrast-black_scale-100.png"
        "VisualStudio.70x70.contrast-black_scale-140.png"
        "VisualStudio.70x70.contrast-black_scale-180.png"
        "VisualStudio.70x70.contrast-black_scale-80.png"
    ]

let sorted =    
    files
    |> Seq.sort
    |> Seq.toArray

(*
val sorted : string [] =
  [|"Blend.150x150.contrast-black_scale-100.png";
    "Blend.150x150.contrast-black_scale-140.png";
    "Blend.150x150.contrast-black_scale-180.png";
    "Blend.150x150.contrast-black_scale-80.png";
    "Blend.70x70.contrast-black_scale-100.png";
    "Blend.70x70.contrast-black_scale-140.png";
    "Blend.70x70.contrast-black_scale-180.png";
    "Blend.70x70.contrast-black_scale-80.png";
    "VisualStudio.150x150.contrast-black_scale-100.png";
    "VisualStudio.150x150.contrast-black_scale-140.png";
    "VisualStudio.150x150.contrast-black_scale-180.png";
    "VisualStudio.150x150.contrast-black_scale-80.png";
    "VisualStudio.70x70.contrast-black_scale-100.png";
    "VisualStudio.70x70.contrast-black_scale-140.png";
    "VisualStudio.70x70.contrast-black_scale-180.png";
    "VisualStudio.70x70.contrast-black_scale-80.png"|]*)

let naturallySorted =    
    files
    |> NaturalOrder.sort
    |> Seq.toArray

(*
val naturallySorted : string [] =
  [|"Blend.70x70.contrast-black_scale-80.png";
    "Blend.70x70.contrast-black_scale-100.png";
    "Blend.70x70.contrast-black_scale-140.png";
    "Blend.70x70.contrast-black_scale-180.png";
    "Blend.150x150.contrast-black_scale-80.png";
    "Blend.150x150.contrast-black_scale-100.png";
    "Blend.150x150.contrast-black_scale-140.png";
    "Blend.150x150.contrast-black_scale-180.png";
    "VisualStudio.70x70.contrast-black_scale-80.png";
    "VisualStudio.70x70.contrast-black_scale-100.png";
    "VisualStudio.70x70.contrast-black_scale-140.png";
    "VisualStudio.70x70.contrast-black_scale-180.png";
    "VisualStudio.150x150.contrast-black_scale-80.png";
    "VisualStudio.150x150.contrast-black_scale-100.png";
    "VisualStudio.150x150.contrast-black_scale-140.png";
    "VisualStudio.150x150.contrast-black_scale-180.png"|]
*)
namespace System
namespace System.Text
namespace System.Text.RegularExpressions
val private regex : Regex

Full name: Script.NaturalOrder.Impl.regex
Multiple items
type Regex =
  new : pattern:string -> Regex + 1 overload
  member GetGroupNames : unit -> string[]
  member GetGroupNumbers : unit -> int[]
  member GroupNameFromNumber : i:int -> string
  member GroupNumberFromName : name:string -> int
  member IsMatch : input:string -> bool + 1 overload
  member Match : input:string -> Match + 2 overloads
  member Matches : input:string -> MatchCollection + 1 overload
  member Options : RegexOptions
  member Replace : input:string * replacement:string -> string + 5 overloads
  ...

Full name: System.Text.RegularExpressions.Regex

--------------------
Regex(pattern: string) : unit
Regex(pattern: string, options: RegexOptions) : unit
type RegexOptions =
  | None = 0
  | IgnoreCase = 1
  | Multiline = 2
  | ExplicitCapture = 4
  | Compiled = 8
  | Singleline = 16
  | IgnorePatternWhitespace = 32
  | RightToLeft = 64
  | ECMAScript = 256
  | CultureInvariant = 512

Full name: System.Text.RegularExpressions.RegexOptions
field RegexOptions.Compiled = 8
val private trimLeadingZeros : s:string -> string

Full name: Script.NaturalOrder.Impl.trimLeadingZeros
val s : string
Multiple items
val string : value:'T -> string

Full name: Microsoft.FSharp.Core.Operators.string

--------------------
type string = String

Full name: Microsoft.FSharp.Core.string
String.TrimStart([<ParamArray>] trimChars: char []) : string
val private toChars : s:string -> char []

Full name: Script.NaturalOrder.Impl.toChars
String.ToCharArray() : char []
String.ToCharArray(startIndex: int, length: int) : char []
val private split : text:string -> string []

Full name: Script.NaturalOrder.Impl.split
val text : string
Regex.Split(input: string) : string []
Regex.Split(input: string, count: int) : string []
Regex.Split(input: string, count: int, startat: int) : string []
module Seq

from Microsoft.FSharp.Collections
val filter : predicate:('T -> bool) -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.filter
property String.Length: int
val toArray : source:seq<'T> -> 'T []

Full name: Microsoft.FSharp.Collections.Seq.toArray
val private compareStrings : s1:string -> s2:string -> int

Full name: Script.NaturalOrder.Impl.compareStrings
val s1 : string
val s2 : string
val isNumeric1 : bool
type Char =
  struct
    member CompareTo : value:obj -> int + 1 overload
    member Equals : obj:obj -> bool + 1 overload
    member GetHashCode : unit -> int
    member GetTypeCode : unit -> TypeCode
    member ToString : unit -> string + 1 overload
    static val MaxValue : char
    static val MinValue : char
    static member ConvertFromUtf32 : utf32:int -> string
    static member ConvertToUtf32 : highSurrogate:char * lowSurrogate:char -> int + 1 overload
    static member GetNumericValue : c:char -> float + 1 overload
    ...
  end

Full name: System.Char
Char.IsDigit(c: char) : bool
Char.IsDigit(s: string, index: int) : bool
val isNumeric2 : bool
Multiple items
type String =
  new : value:char -> string + 7 overloads
  member Chars : int -> char
  member Clone : unit -> obj
  member CompareTo : value:obj -> int + 1 overload
  member Contains : value:string -> bool
  member CopyTo : sourceIndex:int * destination:char[] * destinationIndex:int * count:int -> unit
  member EndsWith : value:string -> bool + 2 overloads
  member Equals : obj:obj -> bool + 2 overloads
  member GetEnumerator : unit -> CharEnumerator
  member GetHashCode : unit -> int
  ...

Full name: System.String

--------------------
String(value: nativeptr<char>) : unit
String(value: nativeptr<sbyte>) : unit
String(value: char []) : unit
String(c: char, count: int) : unit
String(value: nativeptr<char>, startIndex: int, length: int) : unit
String(value: nativeptr<sbyte>, startIndex: int, length: int) : unit
String(value: char [], startIndex: int, length: int) : unit
String(value: nativeptr<sbyte>, startIndex: int, length: int, enc: Text.Encoding) : unit
String.Compare(strA: string, strB: string) : int
String.Compare(strA: string, strB: string, comparisonType: StringComparison) : int
String.Compare(strA: string, strB: string, ignoreCase: bool) : int
String.Compare(strA: string, strB: string, ignoreCase: bool, culture: Globalization.CultureInfo) : int
String.Compare(strA: string, strB: string, culture: Globalization.CultureInfo, options: Globalization.CompareOptions) : int
String.Compare(strA: string, indexA: int, strB: string, indexB: int, length: int) : int
String.Compare(strA: string, indexA: int, strB: string, indexB: int, length: int, comparisonType: StringComparison) : int
String.Compare(strA: string, indexA: int, strB: string, indexB: int, length: int, ignoreCase: bool) : int
String.Compare(strA: string, indexA: int, strB: string, indexB: int, length: int, culture: Globalization.CultureInfo, options: Globalization.CompareOptions) : int
String.Compare(strA: string, indexA: int, strB: string, indexB: int, length: int, ignoreCase: bool, culture: Globalization.CultureInfo) : int
val n1 : string
val n2 : string
val chars1 : char []
val chars2 : char []
val result : int option
val zip : source1:seq<'T1> -> source2:seq<'T2> -> seq<'T1 * 'T2>

Full name: Microsoft.FSharp.Collections.Seq.zip
val tryPick : chooser:('T -> 'U option) -> source:seq<'T> -> 'U option

Full name: Microsoft.FSharp.Collections.Seq.tryPick
val c1 : char
val c2 : char
union case Option.Some: Value: 'T -> Option<'T>
union case Option.None: Option<'T>
val i : int
type private Pair =
  {Name: string;
   Pieces: string [];}

Full name: Script.NaturalOrder.Impl.Pair
Pair.Name: string
Pair.Pieces: string []
module Impl

from Script.NaturalOrder
val sort : names:seq<string> -> seq<string>

Full name: Script.NaturalOrder.sort


 Sort a sequence of strings in natural order.
val names : seq<string>
val map : mapping:('T -> 'U) -> source:seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.map
val name : string
val sortWith : comparer:('T -> 'T -> int) -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.sortWith
val p1 : Pair
val p2 : Pair
type Array =
  member Clone : unit -> obj
  member CopyTo : array:Array * index:int -> unit + 1 overload
  member GetEnumerator : unit -> IEnumerator
  member GetLength : dimension:int -> int
  member GetLongLength : dimension:int -> int64
  member GetLowerBound : dimension:int -> int
  member GetUpperBound : dimension:int -> int
  member GetValue : [<ParamArray>] indices:int[] -> obj + 7 overloads
  member Initialize : unit -> unit
  member IsFixedSize : bool
  ...

Full name: System.Array
val compareWith : comparer:('T -> 'T -> int) -> array1:'T [] -> array2:'T [] -> int

Full name: Microsoft.FSharp.Collections.Array.compareWith
val pair : Pair
val files : string list

Full name: Script.files
val sorted : string []

Full name: Script.sorted
val sort : source:seq<'T> -> seq<'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Seq.sort
val naturallySorted : string []

Full name: Script.naturallySorted
module NaturalOrder

from Script
Raw view Test code New version

More information

Link:http://fssnip.net/7X8
Posted:5 years ago
Author:Jim Foye
Tags: sorting

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.