Dual Pivot Quicksort (2) F#
...habe ich es geschafft
einen Dual Pivot Quicksort zu implementieren.
let rec quicksort list =
match list with
| [] ->
[]
| firstElem::otherElements ->
let mutable secondElem = 0
let mutable v1 = 0
let mutable v2 = 0
if otherElements.Length >= 2 then
let rList = (List.rev otherElements)
let ol = rList.Tail
secondElem <- rList.Head
if firstElem < secondElem then
v1 <- firstElem
v2 <- secondElem
else
v1 <- secondElem
v2 <- firstElem
let part1 = ol |> List.filter( fun e -> e < v1 ) |> quicksort
let part2 = ol |> List.filter( fun e -> e >= v1 && e < v2 ) |> quicksort
let part3 = ol |> List.filter( fun e -> e >= v2) |> quicksort
part1 @ [v1] @ part2 @ [v2] @ part3
else
let smallerElements =
otherElements
|> List.filter (fun e -> e < firstElem)
|> quicksort
let largerElements =
otherElements
|> List.filter (fun e -> e >= firstElem)
|> quicksort
smallerElements @ [firstElem] @largerElements
let rand = System.Random()
let data = List.init 50 (fun _ -> rand.Next ())
printfn "%A" (quicksort data)
System.Console.ReadLine()
Gruß JJR
let rec quicksort list =
match list with
| [] ->
[]
| firstElem::otherElements ->
let mutable secondElem = 0
let mutable v1 = 0
let mutable v2 = 0
if otherElements.Length >= 2 then
let rList = (List.rev otherElements)
let ol = rList.Tail
secondElem <- rList.Head
if firstElem < secondElem then
v1 <- firstElem
v2 <- secondElem
else
v1 <- secondElem
v2 <- firstElem
let part1 = ol |> List.filter( fun e -> e < v1 ) |> quicksort
let part2 = ol |> List.filter( fun e -> e >= v1 && e < v2 ) |> quicksort
let part3 = ol |> List.filter( fun e -> e >= v2) |> quicksort
part1 @ [v1] @ part2 @ [v2] @ part3
else
let smallerElements =
otherElements
|> List.filter (fun e -> e < firstElem)
|> quicksort
let largerElements =
otherElements
|> List.filter (fun e -> e >= firstElem)
|> quicksort
smallerElements @ [firstElem] @largerElements
let rand = System.Random()
let data = List.init 50 (fun _ -> rand.Next ())
printfn "%A" (quicksort data)
System.Console.ReadLine()
Gruß JJR
| Permalink | 
