← All source

C# — Program.cs

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

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

// HW3 - CSC 482 Language Comparison
// Randomized Quicksort in C#, 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 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, as required by DESIGN.md.

using System;
using System.Diagnostics;
using System.IO;

namespace HW3CSharp
{
    internal static class Program
    {
        // Single shared RNG used both for generating test data and for
        // randomized pivot selection, per the assignment's System.Random
        // requirement.
        private static readonly Random Rng = new Random();

        private static void Main()
        {
            const int startN = 1000;
            const int maxIterations = 25;
            const long nCap = 200_000_000L;
            const double timeCutoffSeconds = 4.0;

            string resultsDir = Path.Combine("..", "results");
            // Resolve relative to the repo layout regardless of the
            // working directory the binary is launched from: walk up
            // from the executable's base directory to find HW3/results.
            string resultsPath = ResolveResultsPath();

            Console.WriteLine("n,time_seconds");

            using var writer = new StreamWriter(resultsPath, append: false);
            writer.WriteLine("n,time_seconds");

            long n = startN;
            int iteration = 0;

            while (true)
            {
                iteration++;

                int[] data = GenerateRandomArray((int)n, 0, 1_000_000);

                var sw = Stopwatch.StartNew();
                RandomizedQuicksort(data, 0, data.Length - 1);
                sw.Stop();

                double elapsedSeconds = sw.Elapsed.TotalSeconds;

                string line = $"{n},{elapsedSeconds:R}";
                Console.WriteLine(line);
                writer.WriteLine(line);
                writer.Flush();

                bool timeExceeded = elapsedSeconds > timeCutoffSeconds;
                bool iterationsExhausted = iteration >= maxIterations;
                long nextN = n * 2;
                bool nextExceedsCap = nextN > nCap;

                if (timeExceeded || iterationsExhausted || nextExceedsCap)
                {
                    break;
                }

                n = nextN;
            }

            Console.WriteLine($"Done. Results written to {resultsPath}");
        }

        private static string ResolveResultsPath()
        {
            // AppContext.BaseDirectory is the folder containing the running
            // binary (e.g. csharp/bin/publish/). Walk up until we find a
            // sibling "results" directory next to "csharp", i.e. the HW3
            // root, so the CSV always lands at HW3/results/csharp.csv
            // regardless of where dotnet build/publish placed the binary.
            string dir = AppContext.BaseDirectory;
            for (int i = 0; i < 10; i++)
            {
                string candidate = Path.Combine(dir, "results");
                string csharpSibling = Path.Combine(dir, "csharp");
                if (Directory.Exists(candidate) || Directory.Exists(csharpSibling))
                {
                    return Path.Combine(Directory.Exists(candidate) ? candidate : Path.Combine(dir, "results"), "csharp.csv");
                }
                var parent = Directory.GetParent(dir);
                if (parent == null) break;
                dir = parent.FullName;
            }

            // Fallback: current working directory's ../results
            Directory.CreateDirectory(Path.Combine(Directory.GetCurrentDirectory(), "..", "results"));
            return Path.Combine(Directory.GetCurrentDirectory(), "..", "results", "csharp.csv");
        }

        private static int[] GenerateRandomArray(int n, int minInclusive, int maxExclusive)
        {
            var arr = new int[n];
            for (int i = 0; i < n; i++)
            {
                arr[i] = Rng.Next(minInclusive, maxExclusive);
            }
            return arr;
        }

        // CLRS RANDOMIZED-QUICKSORT(A, p, r)
        private static void RandomizedQuicksort(int[] a, int p, int r)
        {
            if (p < r)
            {
                int q = RandomizedPartition(a, p, r);
                RandomizedQuicksort(a, p, q - 1);
                RandomizedQuicksort(a, q + 1, r);
            }
        }

        // 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.
        private static int RandomizedPartition(int[] a, int p, int r)
        {
            int i = Rng.Next(p, r + 1); // uniform over [p, r]
            Swap(a, i, r);
            return Partition(a, p, r);
        }

        // CLRS PARTITION(A, p, r) - Lomuto partition scheme.
        private static int Partition(int[] a, int p, int r)
        {
            int x = a[r];
            int i = p - 1;
            for (int j = p; j < r; j++)
            {
                if (a[j] <= x)
                {
                    i++;
                    Swap(a, i, j);
                }
            }
            Swap(a, i + 1, r);
            return i + 1;
        }

        private static void Swap(int[] a, int i, int j)
        {
            (a[i], a[j]) = (a[j], a[i]);
        }
    }
}

Read C# report