QuickSort Timing
unknown
python
2 months ago
4.2 kB
3
Indexable
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)
Editor is loading...
Leave a Comment