¿Cuál es la forma más elegante de clasificar burbujas en F #?

Question

¿Cuál es la forma más elegante de clasificar burbujas en F #?

ACTUALIZACIÓN

Como se señala en una de las respuestas, la burbuja de clasificación no es eficiente en un lenguaje funcional, para empezar. Un comentarista con humor cómico también señaló que la clasificación de burbujas solo es apropiada cuando la lista es pequeña y está casi ordenada de todos modos.

Sin embargo, tengo curiosidad por ver cómo se puede escribir un tipo de burbuja inteligente en F #, ya que he hecho géneros de burbuja en C#, C++ y Java EE en el pasado, y como soy un F # novato

Answer 1

utilizando la ordenación de burbuja en un lenguaje funcional no es muy eficiente, porque la implementación tiene que invertir la lista muchas veces (y esto no se puede implementar muy eficientemente para listas inmutables).

De todos modos, el ejemplo de Erlang se puede reescribir a F # como esto:

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 

Por otro lado, se puede aplicar el mismo algoritmo utilizando matrices mutables. Esto será más eficiente y en F # también puede trabajar con matrices si lo desea. La siguiente función crea una copia de la matriz y la ordena.

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