6 people like it.

QuickSort on List

Another version of QuickSort implementation.

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

let anotherQuickSort lst = 
  let rec QuickSortCont l cont =
    match l with
    | [] -> cont []
    | pivot::rest -> 
      let left, right = rest |> List.partition(fun i -> i < pivot)
      QuickSortCont left (fun accLeft -> 
      QuickSortCont right (fun accRight -> cont(accLeft@pivot::accRight)))
  QuickSortCont lst (fun x -> x)

// Test
anotherQuickSort [-22;2;34;-2;0;9;-5;14;-55;74;13]
// Results
[-55; -22; -5; -2; 0; 2; 9; 13; 14; 34; 74]
val anotherQuickSort : lst:'a list -> 'a list (requires comparison)

Full name: Script.anotherQuickSort
val lst : 'a list (requires comparison)
val QuickSortCont : ('b list -> ('b list -> 'c) -> 'c) (requires comparison)
val l : 'b list (requires comparison)
val cont : ('b list -> 'c) (requires comparison)
val pivot : 'b (requires comparison)
val rest : 'b list (requires comparison)
val left : 'b list (requires comparison)
val right : 'b 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 i : 'b (requires comparison)
val accLeft : 'b list (requires comparison)
val accRight : 'b list (requires comparison)
val x : 'a list (requires comparison)
Next Version Raw view Test code New version

More information

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

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.