sorting_analysis.py

import time
import copy

# ==========================================
# 1. SORTING ALGORITHMS
# ==========================================

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

# ==========================================
# 2. EXPERIMENT RUNNER
# ==========================================

def generate_array(size, condition):
    if condition == "sorted":
        return list(range(1, size + 1))
    elif condition == "reverse":
        return list(range(size, 0, -1))

def run_experiment(algo_name, algo_func, arr, runs=3):
    total_time = 0.0
    
    for _ in range(runs):
        # Create a fresh copy of the array for each run so we don't sort an already sorted array
        test_arr = copy.deepcopy(arr) 
        
        # Start timer (using perf_counter for high precision)
        start_time = time.perf_counter()
        
        if algo_name == "Quick Sort":
            test_arr = algo_func(test_arr) # Quick sort implementation used here returns a new array
        else:
            algo_func(test_arr) # Others sort in-place
            
        end_time = time.perf_counter()
        
        total_time += (end_time - start_time)
        
    # Calculate average time in milliseconds
    avg_time_ms = (total_time / runs) * 1000
    return avg_time_ms

# ==========================================
# 3. MAIN EXECUTION
# ==========================================

if __name__ == "__main__":
    algorithms = {
        "Selection Sort": selection_sort,
        "Bubble Sort": bubble_sort,
        "Quick Sort": quick_sort,
        "Merge Sort": merge_sort
    }

    test_cases = [
        {"size": 5, "condition": "sorted"},
        {"size": 5, "condition": "reverse"},
        {"size": 100, "condition": "sorted"},
        {"size": 100, "condition": "reverse"}
    ]

    print("Empirical Analysis of Sorting Algorithms\n")
    print("-" * 50)

    for test in test_cases:
        size = test["size"]
        condition = test["condition"]
        print(f"Test Case: Size = {size}, Condition = {condition.capitalize()}")
        
        base_array = generate_array(size, condition)
        
        for algo_name, algo_func in algorithms.items():
            avg_time = run_experiment(algo_name, algo_func, base_array)
            print(f"  {algo_name:<15}: {avg_time:.6f} ms")
            
        print("-" * 50)