← All source

JavaScript — quicksort.js

node --version

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

'use strict';

/*
 * HW3 - Randomized Quicksort in JavaScript (Node.js)
 *
 * Follows CLRS (Cormen, Leiserson, Rivest & Stein, "Introduction to
 * Algorithms"), Chapter 5, RANDOMIZED-QUICKSORT / RANDOMIZED-PARTITION
 * pseudocode. No external code used - original implementation.
 *
 * At every partition step, a pivot index is chosen uniformly at random
 * from the current subarray range [lo, hi] using Math.random(), swapped
 * into the last position of the subarray, and then a standard Lomuto
 * partition is run around it.
 */

const fs = require('fs');
const path = require('path');

/** Swap arr[i] and arr[j] in place. */
function swap(arr, i, j) {
  const tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
}

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

/**
 * Lomuto partition of arr[lo..hi] around arr[hi] (the pivot).
 * Returns the final index of the pivot.
 */
function partition(arr, lo, hi) {
  const pivot = arr[hi];
  let i = lo - 1;
  for (let j = lo; j < hi; j++) {
    if (arr[j] <= pivot) {
      i++;
      swap(arr, i, j);
    }
  }
  swap(arr, i + 1, hi);
  return i + 1;
}

/**
 * RANDOMIZED-PARTITION: pick a random pivot in [lo, hi], swap it to the
 * end of the subarray, then partition.
 */
function randomizedPartition(arr, lo, hi) {
  const p = randomInt(lo, hi);
  swap(arr, p, hi);
  return partition(arr, lo, hi);
}

/**
 * RANDOMIZED-QUICKSORT: recursive in-place randomized quicksort over
 * arr[lo..hi].
 */
function randomizedQuicksort(arr, lo, hi) {
  if (lo === undefined) lo = 0;
  if (hi === undefined) hi = arr.length - 1;
  if (lo < hi) {
    const q = randomizedPartition(arr, lo, hi);
    randomizedQuicksort(arr, lo, q - 1);
    randomizedQuicksort(arr, q + 1, hi);
  }
  return arr;
}

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

/** Sanity check that arr is sorted ascending. */
function isSorted(arr) {
  for (let i = 1; i < arr.length; i++) {
    if (arr[i - 1] > arr[i]) return false;
  }
  return true;
}

function main() {
  const resultsDir = path.join(__dirname, '..', 'results');
  const csvPath = path.join(resultsDir, 'javascript.csv');
  fs.mkdirSync(resultsDir, { recursive: true });

  const rows = ['n,time_seconds'];
  console.log('n,time_seconds');

  let n = 1000;
  let iterations = 0;
  const MAX_ITERATIONS = 25;
  const MAX_N = 200000000;
  const TIME_LIMIT_SECONDS = 4.0;

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

    const start = process.hrtime.bigint();
    randomizedQuicksort(arr, 0, arr.length - 1);
    const end = process.hrtime.bigint();

    const elapsedSeconds = Number(end - start) / 1e9;

    if (!isSorted(arr)) {
      throw new Error(`Sort verification failed at n=${n}`);
    }

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

    iterations++;

    if (elapsedSeconds > TIME_LIMIT_SECONDS) break;
    if (iterations >= MAX_ITERATIONS) break;
    if (n * 2 > MAX_N) break;

    n *= 2;
  }

  fs.writeFileSync(csvPath, rows.join('\n') + '\n');
  console.log(`\nWrote ${rows.length - 1} rows to ${csvPath}`);
}

main();

Read JavaScript report