3 people like it.
Like the snippet!

Incremental (Functional) QuickSort

Functional quicksort inspired by the Haskell Quick Sort at http://www.haskell.org/haskellwiki/Introduction. Since F# lists aren't lazy, uses sequences instead of lists to be haskell like. Roughly O(n) if you Seq.take 1, full on QS if you enumerate the whole thing.

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

// Functional quick sort - lazy and incremental.
let rec qs (pxs:seq<_>) = 
    seq {
        match Seq.toList pxs with
        | p::xs -> let lesser, greater = List.partition ((>=) p) xs
                   yield! qs lesser; yield p; yield! qs greater
        | _ -> ()
    }

let rand=new System.Random()
let data = Array.init 500000 (fun _ -> rand.Next())
#time
data |> qs |> Seq.take 1    // sub second
#time
#time
data |> qs |> Seq.length    // multiple seconds
#time

val qs : pxs:seq<'a> -> seq<'a> (requires comparison)

Full name: Script.qs

val pxs : seq<'a> (requires comparison)

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

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

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

Full name: Microsoft.FSharp.Collections.seq<_>

module Seq

from Microsoft.FSharp.Collections

val toList : source:seq<'T> -> 'T list

Full name: Microsoft.FSharp.Collections.Seq.toList

val p : 'a (requires comparison)

val xs : 'a list (requires comparison)

val lesser : 'a list (requires comparison)

val greater : 'a list (requires comparison)

Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>

val partition : predicate:('T -> bool) -> list:'T list -> 'T list * 'T list

Full name: Microsoft.FSharp.Collections.List.partition

val rand : System.Random

Full name: Script.rand

namespace System

Multiple items
type Random =
  new : unit -> Random + 1 overload
  member Next : unit -> int + 2 overloads
  member NextBytes : buffer:byte[] -> unit
  member NextDouble : unit -> float

Full name: System.Random

--------------------
System.Random() : unit
System.Random(Seed: int) : unit

val data : int []

Full name: Script.data

module Array

from Microsoft.FSharp.Collections

val init : count:int -> initializer:(int -> 'T) -> 'T []

Full name: Microsoft.FSharp.Collections.Array.init

System.Random.Next() : int
System.Random.Next(maxValue: int) : int
System.Random.Next(minValue: int, maxValue: int) : int

val take : count:int -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.take

val length : source:seq<'T> -> int

Full name: Microsoft.FSharp.Collections.Seq.length

Previous Version Raw view Test code New version

More information

Link:	http://fssnip.net/5d
Posted:	13 years ago
Author:	Tony Lee
Tags:	sequence , sorting