Каков самый изящный способ сортировки пузыря в F#?
Это очень общая ошибка, которая включает в себя множество ошибок. Дополнительную информацию можно найти с помощью fontbakery или Mac Font Validator , каждый из которых предлагает немного различную информацию. Есть и другие проекты, такие как Microsoft Font Validator и OTS, но они предложили значительное улучшение отладки.
По-прежнему не удалось решить общую проблему, но знание более качественных сообщений об ошибках помогает реструктурировать проблему.
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
Tomas