← All source

TypeScript — quicksort.ts

wsl.exe -d Ubuntu -- bash -c "tsc --version && node --version"

wsl.exe -d Ubuntu -- bash -c "cd '/mnt/c/Users/granite/Documents/DSU/Algorithms 482/3/HW3/typescript' && tsc && node quicksort.js"

wsl.exe -d Ubuntu -- bash -c "cd '/mnt/c/Users/granite/Documents/DSU/Algorithms 482/3/HW3/typescript' && npm install --save-dev @types/node"

// HW3 - CSC 482 Language Comparison
// Randomized Quicksort (TypeScript), following CLRS Ch.5
// RANDOMIZED-QUICKSORT / RANDOMIZED-PARTITION pseudocode.
//
// No external code used - original implementation based on CLRS
// RANDOMIZED-QUICKSORT/RANDOMIZED-PARTITION pseudocode (Cormen, Leiserson,
// Rivest & Stein, Introduction to Algorithms, Ch. 5).
//
// Do NOT call Array.prototype.sort - the algorithm is implemented by hand,
// in place, on a number[] array. Math.random() is used both for input data
// generation and for pivot selection.

import * as fs from "fs";
import * as path from "path";

/** Swap the elements at indices i and j of arr in place. */
function swap(arr: number[], i: number, j: number): void {
  const tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
}

/** Uniform random integer in [lo, hi], inclusive, using Math.random(). */
function randomInt(lo: number, hi: number): number {
  return lo + Math.floor(Math.random() * (hi - lo + 1));
}

/**
 * RANDOMIZED-PARTITION(A, p, r):
 * Picks a uniformly random pivot index in [p, r], swaps it into position r,
 * then runs a standard Lomuto partition around A[r]. Returns the final
 * pivot index q such that A[p..q-1] <= A[q] <= A[q+1..r].
 */
function randomizedPartition(arr: number[], p: number, r: number): number {
  const pivotIndex = randomInt(p, r);
  swap(arr, pivotIndex, r);

  const pivotValue = arr[r];
  let i = p - 1;
  for (let j = p; j < r; j++) {
    if (arr[j] <= pivotValue) {
      i++;
      swap(arr, i, j);
    }
  }
  swap(arr, i + 1, r);
  return i + 1;
}

/**
 * RANDOMIZED-QUICKSORT(A, p, r): sorts arr[p..r] in place.
 */
function randomizedQuicksortHelper(arr: number[], p: number, r: number): void {
  if (p < r) {
    const q = randomizedPartition(arr, p, r);
    randomizedQuicksortHelper(arr, p, q - 1);
    randomizedQuicksortHelper(arr, q + 1, r);
  }
}

/** Public entry point: sorts arr (a number[]) in place using randomized quicksort. */
function randomizedQuicksort(arr: number[]): void {
  randomizedQuicksortHelper(arr, 0, arr.length - 1);
}

/** Generate an array of n random integers in [0, 1_000_000) using Math.random(). */
function generateRandomArray(n: number): number[] {
  const arr: number[] = new Array<number>(n);
  for (let i = 0; i < n; i++) {
    arr[i] = Math.floor(Math.random() * 1_000_000);
  }
  return arr;
}

/** Convert a BigInt nanosecond duration to a floating-point seconds value. */
function nanosToSeconds(nanos: bigint): number {
  return Number(nanos) / 1e9;
}

function main(): void {
  const resultsDir = path.join(__dirname, "..", "results");
  if (!fs.existsSync(resultsDir)) {
    fs.mkdirSync(resultsDir, { recursive: true });
  }
  const csvPath = path.join(resultsDir, "typescript.csv");
  const rows: string[] = ["n,time_seconds"];

  console.log("n,time_seconds");

  let n = 1000;
  let iterations = 0;
  const MAX_ITERATIONS = 25;
  const TIME_CUTOFF_SECONDS = 4.0;
  const MAX_N = 200_000_000;

  while (true) {
    const arr = generateRandomArray(n);

    const start = process.hrtime.bigint();
    randomizedQuicksort(arr);
    const end = process.hrtime.bigint();

    const elapsedSeconds = nanosToSeconds(end - start);
    iterations++;

    const row = `${n},${elapsedSeconds.toFixed(6)}`;
    rows.push(row);
    console.log(row);

    // Write results incrementally so partial progress is preserved.
    fs.writeFileSync(csvPath, rows.join("\n") + "\n");

    if (elapsedSeconds > TIME_CUTOFF_SECONDS) {
      break;
    }
    if (iterations >= MAX_ITERATIONS) {
      break;
    }
    if (n * 2 > MAX_N) {
      break;
    }
    n *= 2;
  }
}

main();

Read TypeScript report