← All source

Java — Main.java

javac Main.java

java Main

wsl.exe -d Ubuntu -- bash -c "cd '/mnt/c/Users/granite/Documents/DSU/Algorithms 482/3/HW3/java' && javac Main.java && java Main"

import java.io.FileWriter;
import java.io.IOException;
import java.util.Locale;
import java.util.Random;

/**
 * HW3 - Language Comparison: Randomized Quicksort in Java.
 *
 * Implementation follows CLRS (Cormen, Leiserson, Rivest & Stein),
 * Introduction to Algorithms, Ch. 5, RANDOMIZED-QUICKSORT /
 * RANDOMIZED-PARTITION pseudocode. No external code used - original
 * implementation based on that pseudocode. No sorting-library shortcuts
 * (Arrays.sort / Collections.sort are not used anywhere in this file).
 *
 * See ../DESIGN.md for the full shared experiment protocol.
 */
public class Main {

    // Single Random instance used for both data generation and pivot
    // selection, per java.util.Random (standard library only).
    private static final Random RNG = new Random();

    public static void main(String[] args) throws IOException {
        System.out.println("JDK version: " + System.getProperty("java.version"));

        StringBuilder csv = new StringBuilder();
        csv.append("n,time_seconds\n");
        System.out.println("n,time_seconds");

        long n = 1000;
        int iterations = 0;
        final long MAX_N = 200_000_000L;
        final double TIME_LIMIT_SECONDS = 4.0;
        final int MAX_ITERATIONS = 25;

        while (true) {
            int[] arr = generateRandomArray((int) n, 1_000_000);

            long start = System.nanoTime();
            randomizedQuicksort(arr, 0, arr.length - 1);
            long end = System.nanoTime();

            double elapsedSeconds = (end - start) / 1_000_000_000.0;

            // Sanity check the sort is correct (cheap, not timed).
            assertSorted(arr);

            String row = n + "," + String.format(Locale.US, "%.9f", elapsedSeconds);
            csv.append(row).append("\n");
            System.out.println(row);

            iterations++;

            boolean overTimeLimit = elapsedSeconds > TIME_LIMIT_SECONDS;
            boolean overIterations = iterations >= MAX_ITERATIONS;
            long nextN = n * 2;
            boolean nextExceedsCap = nextN > MAX_N;

            if (overTimeLimit || overIterations || nextExceedsCap) {
                break;
            }

            n = nextN;
        }

        String resultsPath = "../results/java.csv";
        try (FileWriter fw = new FileWriter(resultsPath)) {
            fw.write(csv.toString());
        }
        System.out.println("Results written to " + resultsPath);
    }

    /** Generates an array of n random ints uniformly in [0, bound). */
    private static int[] generateRandomArray(int n, int bound) {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = RNG.nextInt(bound);
        }
        return arr;
    }

    /**
     * RANDOMIZED-QUICKSORT(A, p, r) from CLRS.
     * Sorts A[p..r] in place.
     */
    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);
        }
    }

    /**
     * RANDOMIZED-PARTITION(A, p, r) from CLRS.
     * Picks a pivot index uniformly at random in [p, r], swaps it into the
     * last position (A[r]), then runs the standard Lomuto PARTITION.
     */
    private static int randomizedPartition(int[] a, int p, int r) {
        int i = p + RNG.nextInt(r - p + 1); // uniform in [p, r]
        swap(a, i, r);
        return partition(a, p, r);
    }

    /** PARTITION(A, p, r) from CLRS - Lomuto partition scheme. */
    private static int partition(int[] a, int p, int r) {
        int x = a[r]; // pivot
        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) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    private static void assertSorted(int[] a) {
        for (int i = 1; i < a.length; i++) {
            if (a[i - 1] > a[i]) {
                throw new IllegalStateException("Array not sorted at index " + i);
            }
        }
    }
}

Read Java report