← All source

F# — Program.fs

wsl.exe -d Ubuntu -- bash -c "cd '/mnt/c/Users/granite/Documents/DSU/Algorithms 482/3/HW3/fsharp' && dotnet new console -lang F# -o . --force"

wsl.exe -d Ubuntu -- bash -c "cd '/mnt/c/Users/granite/Documents/DSU/Algorithms 482/3/HW3/fsharp' && dotnet build -c Release -o bin/publish"

wsl.exe -d Ubuntu -- bash -c "cd '/mnt/c/Users/granite/Documents/DSU/Algorithms 482/3/HW3/fsharp' && dotnet ./bin/publish/fsharp.dll"

// HW3 - CSC 482 Language Comparison
// Randomized Quicksort in F#, following CLRS Ch. 5 RANDOMIZED-QUICKSORT /
// RANDOMIZED-PARTITION pseudocode (Cormen, Leiserson, Rivest & Stein,
// "Introduction to Algorithms"). Original implementation - no external
// code copied. In-place Lomuto partition operating on a mutable int[]
// (the standard, idiomatic approach for this kind of performance-sensitive
// in-place algorithm even in a functional-first language like F#), with a
// uniformly random pivot chosen (and swapped into the last position of the
// current subarray) at every partition step, using System.Random for both
// pivot selection and test-data generation, per DESIGN.md.

open System
open System.Diagnostics
open System.IO

// Single shared RNG used both for generating test data and for randomized
// pivot selection.
let rng = Random()

/// Swap two elements of a mutable int array in place.
let inline swap (a: int[]) (i: int) (j: int) =
    let tmp = a.[i]
    a.[i] <- a.[j]
    a.[j] <- tmp

/// CLRS PARTITION(A, p, r) - Lomuto partition scheme.
let partition (a: int[]) (p: int) (r: int) : int =
    let x = a.[r]
    let mutable i = p - 1
    for j in p .. r - 1 do
        if a.[j] <= x then
            i <- i + 1
            swap a i j
    swap a (i + 1) r
    i + 1

/// CLRS RANDOMIZED-PARTITION(A, p, r): pick a uniformly random index in
/// [p, r], swap it into the last position, then run the standard Lomuto
/// PARTITION.
let randomizedPartition (a: int[]) (p: int) (r: int) : int =
    let i = rng.Next(p, r + 1) // uniform over [p, r], Next's upper bound is exclusive
    swap a i r
    partition a p r

/// CLRS RANDOMIZED-QUICKSORT(A, p, r)
let rec randomizedQuicksort (a: int[]) (p: int) (r: int) : unit =
    if p < r then
        let q = randomizedPartition a p r
        randomizedQuicksort a p (q - 1)
        randomizedQuicksort a (q + 1) r

/// Generate a fresh array of n random ints in [minInclusive, maxExclusive).
let generateRandomArray (n: int) (minInclusive: int) (maxExclusive: int) : int[] =
    Array.init n (fun _ -> rng.Next(minInclusive, maxExclusive))

/// Resolve HW3/results/fsharp.csv relative to the running binary's location,
/// walking up from AppContext.BaseDirectory (e.g. fsharp/bin/publish/) until
/// a sibling "results" directory (or "fsharp" directory, i.e. the HW3 root)
/// is found, so the CSV lands in the shared results/ folder regardless of
/// the working directory the binary is launched from.
let resolveResultsPath () : string =
    let rec walkUp (dir: string) (attemptsLeft: int) : string option =
        if attemptsLeft <= 0 then
            None
        else
            let candidate = Path.Combine(dir, "results")
            let fsharpSibling = Path.Combine(dir, "fsharp")
            if Directory.Exists candidate then
                Some(Path.Combine(candidate, "fsharp.csv"))
            elif Directory.Exists fsharpSibling then
                let resultsDir = Path.Combine(dir, "results")
                Directory.CreateDirectory(resultsDir) |> ignore
                Some(Path.Combine(resultsDir, "fsharp.csv"))
            else
                match Directory.GetParent(dir) with
                | null -> None
                | parent -> walkUp parent.FullName (attemptsLeft - 1)

    match walkUp AppContext.BaseDirectory 10 with
    | Some p -> p
    | None ->
        let fallbackDir = Path.Combine(Directory.GetCurrentDirectory(), "..", "results")
        Directory.CreateDirectory(fallbackDir) |> ignore
        Path.Combine(fallbackDir, "fsharp.csv")

[<EntryPoint>]
let main _argv =
    let startN = 1000L
    let maxIterations = 25
    let nCap = 200_000_000L
    let timeCutoffSeconds = 4.0

    let resultsPath = resolveResultsPath ()

    printfn "n,time_seconds"

    use writer = new StreamWriter(resultsPath, false)
    writer.WriteLine("n,time_seconds")

    let mutable n = startN
    let mutable iteration = 0
    let mutable keepGoing = true

    while keepGoing do
        iteration <- iteration + 1

        let data = generateRandomArray (int n) 0 1_000_000

        let sw = Stopwatch.StartNew()
        randomizedQuicksort data 0 (data.Length - 1)
        sw.Stop()

        let elapsedSeconds = sw.Elapsed.TotalSeconds

        let line = sprintf "%d,%s" n (elapsedSeconds.ToString("R"))
        printfn "%s" line
        writer.WriteLine(line)
        writer.Flush()

        let timeExceeded = elapsedSeconds > timeCutoffSeconds
        let iterationsExhausted = iteration >= maxIterations
        let nextN = n * 2L
        let nextExceedsCap = nextN > nCap

        if timeExceeded || iterationsExhausted || nextExceedsCap then
            keepGoing <- false
        else
            n <- nextN

    printfn "Done. Results written to %s" resultsPath
    0

Read F# report