Was ist die eleganteste Art der Blasensortierung in F #?

Question

Was ist die eleganteste Art der Blasensortierung in F #?

UPDATE

Wie in einer der Antworten darauf hingewiesen, ist Blasensortierung mit nicht effizient in einer funktionalen Sprache zu beginnen. Ein humoristisch-zynischer Kommentator wies auch darauf hin, dass die Blasensortierung nur dann sinnvoll ist, wenn die Liste klein ist und ohnehin fast sortiert ist.

Allerdings bin ich neugierig zu sehen, wie eine clevere Bubble-Sortierung in F # geschrieben werden kann, da ich in der Vergangenheit Bubble-Sortierungen in C#, C++ und Java EE gemacht habe, und da ich ein F # bin Neuling.

Answer 1

Verwendung von Bubble-Sort in einer funktionalen Sprache ist nicht sehr effizient, weil die Implementierung die Liste mehrmals umkehren muss (und dies kann nicht wirklich effizient für unveränderliche Listen implementiert werden).

Wie auch immer, kann das Beispiel von Erlang geschrieben wie diese Fis wird:

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 

Auf der anderen Seite, können Sie mit dem gleichen Algorithmus änderbare Arrays implementieren. Dies wird effizienter und in F # können Sie auch mit Arrays arbeiten, wenn Sie möchten. Die folgende Funktion erstellt eine Kopie des Arrays und sortiert sie.

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