Cách phân loại bong bóng tốt nhất trong F # là gì?

Question

Cách phân loại bong bóng thanh lịch nhất trong F # là gì?

CẬP NHẬT

Như đã chỉ ra ở một trong những câu trả lời, bong bóng phân loại là không hiệu quả trong một ngôn ngữ chức năng để bắt đầu với. Một nhà bình luận hài hước, hoài nghi cũng chỉ ra rằng việc phân loại bong bóng chỉ thích hợp khi danh sách nhỏ và gần như được sắp xếp. Tuy nhiên, tôi tò mò muốn xem cách một loại bong bóng thông minh có thể được viết bằng F #, vì tôi đã thực hiện các loại bong bóng trong C#, C++ và Java EE trong quá khứ và vì tôi là một F # người mới.

Answer 1

sử dụng loại bong bóng trong ngôn ngữ chức năng không hiệu quả lắm, vì việc triển khai phải đảo ngược danh sách nhiều lần (và điều này không thể thực sự được triển khai hiệu quả cho danh sách không thể thay đổi).

Dù sao, ví dụ từ Erlang có thể được viết lại để F # như thế này:

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 

Ở phía bên kia, bạn có thể thực hiện cùng một thuật toán sử dụng mảng có thể thay đổi. Điều này sẽ hiệu quả hơn và trong F # bạn cũng có thể làm việc với các mảng nếu bạn muốn. Hàm sau tạo một bản sao của mảng và sắp xếp nó.

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