« Dual Quicksort f# | Main| »

Dual Pivot Quicksort (2) F#

10
Kategorie  
So nach zähen Verhandlungen mit dem Compiler....
...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

Mach einen Kommentar

:-D:-o:-p:-x:-(:-):-\:angry::cool::cry::emb::grin::huh::laugh::lips::rolleyes:;-)

Powered By

Domino BlogSphere
Version 3.0.2