quick_sort_time_simulation

quick_sort_time.py

import random
import numpy as np

def simulate_T(n):
    if n <= 1:
        return 0
    # the pivot may end up randomly anywhere from 0 to n-1
    pivot_index = random.randint(0, n - 1)

    first_half = simulate_T(pivot_index)
    second_half = simulate_T(n - pivot_index - 1)
    return (n - 1) + first_half + second_half

if __name__ == "__main__":
    # use n = 100
    # sample it 1000 times
    simulation_results = [simulate_T(100) for _ in range(1000)]
    # get the mean and standard deviation
    mean = sum(simulation_results) / len(simulation_results)
    variance = sum((x - mean) ** 2 for x in simulation_results) / len(simulation_results)
    std_dev = variance ** 0.5

    # plot the simulated points, mean, and standard deviation
    import matplotlib.pyplot as plt
    plt.hist(simulation_results, bins=30, alpha=0.7, color='blue')
    plt.axvline(mean, color='red', linestyle='dashed', linewidth=1)
    plt.axvline(mean + std_dev, color='green', linestyle='dashed', linewidth=1)
    plt.axvline(mean - std_dev, color='green', linestyle='dashed', linewidth=1)
    plt.title('Simulation of T(n) for n=100, 1000 samples')
    plt.xlabel('T(n)')
    plt.ylabel('Frequency')
    plt.legend(['Mean', 'Mean + Std Dev', 'Mean - Std Dev'])
    plt.show()

    # now, simulate it for n = 2, 3, 4, all the way to 100
    # for each n, simulate it 10n times
    n_values = list(range(2, 101))
    means = []
    stds = []
    simulated_resultss = []
    for n in n_values:
        simulation_results = [simulate_T(n) for _ in range(10 * n)]
        simulated_resultss.append(simulation_results)
        mean = sum(simulation_results) / len(simulation_results)
        means.append(mean)
        variance = sum((x - mean) ** 2 for x in simulation_results) / len(simulation_results)
        std_dev = variance ** 0.5
        stds.append(std_dev)

    import numpy as np
    import matplotlib.pyplot as plt

    n_values = list(range(2, 101))

    # --- your simulation (already computed) ---
    # simulated_resultss: list of lists, each inner list has 10*n samples for that n
    # means, stds: lists aligned with n_values

    # 1) simulated mean (blue line)
    plt.plot(n_values, means, color='green', label='Simulated Mean')

    # 2) ±1 std dev tube (transparent)
    means_arr = np.array(means)
    stds_arr = np.array(stds)
    plt.fill_between(
        n_values,
        means_arr - stds_arr,
        means_arr + stds_arr,
        color='green',
        alpha=0.20,
        label='±1 Std Dev'
    )

    # 3) theoretical curve (red line)
    theoretical_values = [n * np.log2(n) for n in n_values]
    plt.plot(n_values, theoretical_values, color='red', label='Theoretical T(n) = n * log2(n)')

    # 4) jittered individual samples (transparent)
    rng = np.random.default_rng(0)              # fixed seed for reproducibility; remove if you want fresh jitter each run
    jitter_scale = 0.15                         # horizontal jitter in x-units
    max_points_per_n = None                     # or set e.g. 400 to subsample dense clouds

    for n, samples in zip(n_values, simulated_resultss):
        x0 = n
        k = len(samples)
        if max_points_per_n is not None and k > max_points_per_n:
            idx = rng.choice(k, size=max_points_per_n, replace=False)
            y = np.array(samples)[idx]
            k = max_points_per_n
        else:
            y = np.array(samples)
        x = x0 + rng.normal(0.0, jitter_scale, size=k)
        plt.scatter(x, y, s=8, alpha=0.15, color='blue', linewidths=0)  # tiny, transparent dots

    # cosmetics
    plt.title('Mean, Std Tube, and Samples for T(n) (n=2..100)')
    plt.xlabel('n')
    plt.ylabel('T(n)')
    plt.legend()
    plt.tight_layout()
    plt.show()