← All source

Python — quicksort.py

wsl.exe -d Ubuntu -- bash -c "cd '/mnt/c/Users/granite/Documents/DSU/Algorithms 482/3/HW3/python' && python3 quicksort.py"

$ python3 --version
Python 3.14.4

"""
Randomized Quicksort timing harness (CSC 482 HW3 - Language Comparison).

Algorithm: CLRS RANDOMIZED-QUICKSORT / RANDOMIZED-PARTITION (Ch. 5).
In-place quicksort on a Python list of ints; at every partition step the
pivot index is chosen uniformly at random from the current subarray range
using the standard library `random` module, swapped into the last position,
and a standard Lomuto partition is run around it.

No external code used - original implementation based on CLRS
RANDOMIZED-QUICKSORT pseudocode. No sorting-library shortcuts
(list.sort()/sorted() are never called).
"""

import csv
import os
import random
import sys
import time


def randomized_partition(a, lo, hi):
    """Lomuto partition of a[lo..hi] around a uniformly random pivot.

    Chooses a random index in [lo, hi], swaps it into position hi (the
    CLRS RANDOMIZED-PARTITION step), then runs the standard Lomuto
    partition, returning the pivot's final index.
    """
    pivot_index = random.randint(lo, hi)
    a[pivot_index], a[hi] = a[hi], a[pivot_index]

    pivot = a[hi]
    i = lo - 1
    for j in range(lo, hi):
        if a[j] <= pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[hi] = a[hi], a[i + 1]
    return i + 1


def randomized_quicksort(a, lo=0, hi=None):
    """In-place CLRS RANDOMIZED-QUICKSORT on a[lo..hi] (inclusive)."""
    if hi is None:
        hi = len(a) - 1
    if lo < hi:
        p = randomized_partition(a, lo, hi)
        randomized_quicksort(a, lo, p - 1)
        randomized_quicksort(a, p + 1, hi)


def generate_random_list(n, lo=0, hi=1_000_000):
    return [random.randrange(lo, hi) for _ in range(n)]


def main():
    script_dir = os.path.dirname(os.path.abspath(__file__))
    results_dir = os.path.abspath(os.path.join(script_dir, "..", "results"))
    os.makedirs(results_dir, exist_ok=True)
    csv_path = os.path.join(results_dir, "python.csv")

    n = 1000
    max_iterations = 25
    time_cutoff = 4.0
    n_cap = 200_000_000

    rows = []
    print("n,time_seconds")

    iteration = 0
    while True:
        iteration += 1

        data = generate_random_list(n)

        start = time.perf_counter()
        try:
            randomized_quicksort(data)
        except RecursionError as exc:
            print(f"ANOMALY: RecursionError at n={n}: {exc}", file=sys.stderr)
            break
        elapsed = time.perf_counter() - start

        rows.append((n, elapsed))
        print(f"{n},{elapsed:.6f}")

        # Sanity check the sort is actually correct (not timed; cheap relative
        # to the sort itself only for small n, but useful during development).
        # Left in place as a lightweight correctness guard.
        # (Comment out if it ever becomes a measurable overhead concern.)
        # assert all(data[i] <= data[i + 1] for i in range(len(data) - 1))

        if elapsed > time_cutoff:
            print(f"Stopping: elapsed {elapsed:.3f}s exceeded {time_cutoff}s cutoff at n={n}")
            break
        if iteration >= max_iterations:
            print(f"Stopping: reached {max_iterations} iterations")
            break
        if n * 2 > n_cap:
            print(f"Stopping: next n ({n * 2}) would exceed cap {n_cap}")
            break

        n *= 2

    with open(csv_path, "w", newline="") as f:
        writer = csv.writer(f)
        writer.writerow(["n", "time_seconds"])
        for row_n, row_t in rows:
            writer.writerow([row_n, f"{row_t:.6f}"])

    print(f"\nWrote {len(rows)} rows to {csv_path}")


if __name__ == "__main__":
    main()

Read Python report