6 people like it.

QuickSort on List

Another version of QuickSort implementation.

1: 
2: 
3: 
4: 
5: 
6: 
7: 
8: 
9: 
let rec qsort  = function
    | [] ->  []
    | pivot::rest -> let left, right = rest |> List.partition(fun i -> i < pivot)
                     (qsort left) @ [pivot] @ qsort right

// Test
qsort [-22;2;34;-2;0;9;-5;14;-55;74;13]
// Results
[-55; -22; -5; -2; 0; 2; 9; 13; 14; 34; 74]
val qsort : _arg1:'a list -> 'a list (requires comparison)
val pivot : 'a (requires comparison)
val rest : 'a list (requires comparison)
val left : 'a list (requires comparison)
val right : 'a 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 partition : predicate:('T -> bool) -> list:'T list -> 'T list * 'T list
val i : 'a (requires comparison)

More information

Link:http://fssnip.net/eh
Posted:2 years ago
Author:Shankar V
Tags: algorithms , quicksort , list