What is the most elegant way of bubble-sorting in F#?

Question

What is the most elegant way of bubble-sorting in F#?

UPDATE

As pointed out in one of the answers, bubble sorting isn't efficient in a functional language to begin with. A humourously-cynical commenter also pointed out that bubble sorting is only appropriate when the list is small and it's almost sorted anyway.

However, I'm curious to see how a clever bubble-sort can be written in F#, since I've done bubble sorts in C#, C++, and JEE in the past, and since I'm an F# newbie.

Thanks!

KA

Answer 1

Hi, 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

On the other side, 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

Tomas