`let quicksortM M fn a =`

let N = Array.length a - 1

let mutable stack = [0,0]

let mutable l = 0

let mutable r = N

let swap x y =

let t = a.[ x ]

a.[ x ] <- a.[ y ]

a.[ y ] <- t

let sort3 x y z =

if a.[ x ] > a.[ y ] then swap x y

if a.[ x ] > a.[ z ] then swap x z

if a.[ y ] > a.[ z ] then swap y z

while stack <> [] do

let count = (r-l)+1

According to the author,

[this] Quicksort is almost 2x faster than the .NET library sort above 1,000 elements in the random and forward ordered cases

**UPDATE**:

Using bubble sort in a functional language isn't very efficient, because the implementation has to reverse the list many times (and this can't be really implemented very efficiently for immutable lists).

Anyway, the example from Erlang can be rewritten to F# like this:

**let sort l =**

let rec sortUtil acc rev l =

match l, rev with

[], true -> acc > List.rev

[], false -> acc > List.rev > sortUtil [] true

x::y::tl, _ when x > y -> sortUtil (y::acc) false (x::tl)

hd::tl, _ -> sortUtil (hd::acc) rev tl

sortUtil [] true l

let rec sortUtil acc rev l =

match l, rev with

[], true -> acc > List.rev

[], false -> acc > List.rev > sortUtil [] true

x::y::tl, _ when x > y -> sortUtil (y::acc) false (x::tl)

hd::tl, _ -> sortUtil (hd::acc) rev tl

sortUtil [] true l

On the other hand, you can implement the same algorithm using mutable arrays. This will be more efficient and in F# you can work with arrays too if you want. The following function creates a copy of the array and sorts it.

**let sort (arr:**

**'a[]) =**

let arr = arr > Array.copy

let swap i j = let tmp = arr.[i] in arr.[i] <- arr.[j]; arr.[j] <- tmp

for i = arr.Length - 1 downto 0 do

for j = 1 to i do

if (arr.[j - 1] > arr.[j]) then swap (j-1) j

arr

let arr = arr > Array.copy

let swap i j = let tmp = arr.[i] in arr.[i] <- arr.[j]; arr.[j] <- tmp

for i = arr.Length - 1 downto 0 do

for j = 1 to i do

if (arr.[j - 1] > arr.[j]) then swap (j-1) j

arr

Crazy, I didn't know this functional stuff would be that fast. It's hard to get used to though - I miss my Fortran :-)

ReplyDeleteafter object oriented programming it is really hard to wrap your head around functional, at least for me =) the quick sort code looks very clean and neat though, well done

ReplyDelete