« Dual Quicksort f# | Main| »

Dual Pivot Quicksort (2) F#

10
Category  
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

Post A Comment

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

Amazon


Impressum

Firmenname: Peanuts-Soft
Straße Nummer: Biinger Strasse 8
PLZ Ort: 55263 Wackernheim
Telefon: +491772134526
E-Mail: joerg.reck @ peanuts-soft.de
Disclaimer: Peanuts-Soft übernimmt keine Garantie dafür, dass die auf dieser Website bereitgestellten Informationen vollständig, richtig und stets aktuell sind. Dies gilt auch für alle Links, auf die verwiesen wird. Peanuts-Soft ist für die Inhalte, auf die per Link verwiesen wird, nicht verantwortlich. Peanuts-Soft haftet nicht für konkrete, mittelbare und unmittelbare Schäden oder Schäden, die durch fehlende Nutzungsmöglichkeiten, Datenverluste oder entgangene Gewinne – sei es aufgrund der Nichteinhaltung vertraglicher Verpflichtungen, durch Fahrlässigkeit oder eine andere unerlaubte Handlung – im Zusammenhang mit der Nutzung von Dokumenten oder Informationen bzw. der Erbringung von Dienstleistungen entstehen, die auf dieser Web Site zugänglich sind.
Datenschutz: Inhalt und Gestaltung der Internetseiten sind urheberrechtlich geschützt. Eine Vervielfältigung der Seiten oder deren Inhalte bedarf der vorherigen schriftlichen Zustimmung von Peanuts-Soft.


Locations of visitors to this page

Powered By

Domino BlogSphere
Version 3.0.2