Какой самый элегантный способ сортировки пузырьков в F #?

Question

Какой самый элегантный способ сортировки пузырьков в F #?

UPDATE

Как указано в одном из ответов, пузырьковая сортировка с самого начала неэффективна на функциональном языке. Юмористически-циничный комментатор также указал, что пузырьковая сортировка подходит только тогда, когда список небольшой и в любом случае он почти отсортирован.

Однако мне любопытно посмотреть, как умная сортировка пузырьков может быть написана на F #, так как в прошлом я выполнял сортировку пузырьков на C #, C ++ и Java EE, и так как я новичок в F # .

Answer 1

использование пузырьковой сортировки на функциональном языке не очень эффективно, потому что реализация вынуждена многократно изменять список (и это не может быть реализовано очень эффективно для неизменяемых списков).

В любом случае, пример из Erlang можно переписать на F # следующим образом:

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

С другой стороны, вы можете реализовать тот же алгоритм, используя изменяемые массивы. Это будет более эффективно, и в F # вы также можете работать с массивами, если хотите. Следующая функция создает копию массива и сортирует ее.

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

Томас