QuickSort Timing

import math
import time
import random
import matplotlib.pyplot as plt

basicOpsCounted = 0

def reset():
    global basicOpsCounted
    basicOpsCounted = 0

def basicOps():
    return basicOpsCounted

def quickSort(a, low, high):
    global basicOpsCounted
    if (low >= high or low < 0):
        return
    p = partition(a, low, high)

    quickSort(a, low, p - 1)
    quickSort(a, p + 1, high)
pass

def partition(a, low, high):
    pivot = a[high]
    global basicOpsCounted
    i = low - 1
    for j in range(low, high):
        basicOpsCounted += 1
        if a[j] <= pivot:
            i = i + 1
            a[i], a[j] = a[j], a[i]    
    i = i + 1
    a[i], a[high] = a[high], a[i]
    return i
pass


def generate_random_list(n):
    return [random.randint(1, 10000) for _ in range(n)]

def run_quicksort_tests(k_values):
    sizes = []
    times = []
    operations = []
    nlogn_values = []
    estimated_times = []  

    for k in k_values:
        n = 2 ** k
        arr = generate_random_list(n)
        reset()
        start_time = time.time()
        quickSort(arr, 0, n - 1)
        end_time = time.time()

        sizes.append(n)
        time_in_ms = (end_time - start_time) * 1000
        times.append(time_in_ms)
        operations.append(basicOps())
        nlogn_values.append(n * math.log2(n)) 

        print(f"n = {n}: Time = {time_in_ms:.6f} ms, Basic Ops = {basicOps()}")

    estimated_times, c_op_estimate, c_time_estimate = calculate_constant_c(operations, nlogn_values, sizes, times)

    plt.figure(figsize=(18, 12))

    # Plot for execution time and basic operations
    plt.subplot(2, 2, 1)
    plt.plot(sizes, times, marker='o', label='Actual Time')
    plt.plot(sizes, estimated_times, marker='x', linestyle='--', label='Estimated Time (n log n)')
    plt.xlabel('Input Size (n)')
    plt.ylabel('Time (seconds)')
    plt.xscale('log')
    plt.yscale('log')
    plt.title('QuickSort Actual vs Estimated Time')
    plt.legend()

    # Plot for basic operations vs n, with n*log(n) for comparison
    plt.subplot(2, 2, 2)
    plt.plot(sizes, operations, marker='o', label='Basic Operations', color='r')  
    plt.plot(sizes, nlogn_values, marker='x', linestyle='--', label='Estimated n*log(n)', color='b')  
    plt.xlabel('Input Size (n)')
    plt.ylabel('Basic Operations / n*log(n)')
    plt.xscale('log')
    plt.yscale('log')
    plt.title('Basic Operations vs Input Size (n) with n*log(n)')
    plt.legend()

    # Plot for correlation between nlogn_values and operations
    plt.subplot(2, 2, 3)
    plt.plot(sizes, nlogn_values, marker='x', linestyle='--', label='n*log(n)', color='b')
    plt.plot(sizes, operations, marker='o', label='Basic Operations', color='r')
    plt.xlabel('Input Size (n)')
    plt.ylabel('Operations / n*log(n)')
    plt.xscale('log')
    plt.yscale('log')
    plt.title('n*log(n) vs Basic Operations')
    plt.legend()

    # Plot for correlation between nlogn_values and operations
    plt.subplot(2, 2, 4)
    plt.plot(sizes, nlogn_values, marker='x', linestyle='--', label='Estimated n*log(n)', color='b')
    plt.plot(sizes, operations, marker='o', label='Basic Operations', color='g')  
    plt.xlabel('Input Size (n)')
    plt.ylabel('Operations / n*log(n)')
    plt.xscale('log')
    plt.yscale('log')
    plt.title('Correlation between n*log(n) and Basic Operations')
    plt.legend()

    plt.tight_layout()
    plt.show()

def calculate_constant_c(operations, nlogn_values, sizes, times):
    c_op_values = [ops / nlogn for ops, nlogn in zip(operations, nlogn_values)]
    c_op_estimate = sum(c_op_values) / len(c_op_values)
    
    c_time_values = [time / nlogn for time, nlogn in zip(times, nlogn_values)]
    c_time_estimate = sum(c_time_values) / len(c_time_values)

    print(f"Estimated constant c (Operations) ≈ {c_op_estimate:.4f}")
    print(f"Estimated constant c (Time) ≈ {c_time_estimate:.8f}")

    estimated_times = [c_time_estimate * nlogn for nlogn in nlogn_values]

    return estimated_times, c_op_estimate, c_time_estimate

k_values = [10, 15, 20]
run_quicksort_tests(k_values)