Sorting_Algorithms.py

import random
import time
import tracemalloc
from datetime import datetime, timedelta
import matplotlib.pyplot as plt
import csv

def bubble_sort(arr):
    result=arr.copy()
    n= len(result)

    for i in range(n):
        swapped = False
        for j in range(n-i-1):
                if result[j] > result[j+1]:
                     result[j] ,result[j+1]= result[j+1], result[j]
                     swapped=True
        if not swapped:
            break

    return result

def merge_sort(arr):
    if len(arr)<=1:
        return arr.copy()
    mid=len(arr)//2
    left_half=merge_sort(arr[:mid])
    right_half=merge_sort(arr[mid:])

    return merge(left_half,right_half)

def merge(left ,right):
    merged=[]
    i=0
    j=0
    while i< len(left) and j< len(right):
        if left[i]<=right[j]:
            merged.append(left[i])
            i+=1

        else:
            merged.append(right[j])
            j+=1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged
def quick_sort(arr):
    if len(arr)<=1:
        return arr.copy()
    pivot=arr[len(arr)//2]
    left=[x for x in arr if x<pivot] #smaller  elements
    middle = [x for x in arr if x ==pivot]
    right = [x for x in arr if x > pivot]#bigger elements
    return quick_sort(left)+middle + quick_sort(right)

def generate_random_data(size):
    return [random.randint(1,20000)
            for _ in range(size)]
def generate_sorted_data(size):
    return list(range(size))
def generate_reverse_data(size):
    return list(range(size,0,-1))
def generate_nearly_sorted_data(size):
    data=list(range(size))
    swaps=max(1,size//10)
    for _ in range (swaps):
        i=random.randint(0,size-1)
        j=random.randint(0,size-1)
        data[i],data[j]=data[j],data[i]

    return data

def generate_timestamp_data(size):
    base_timestamp=datetime(2026,4,7,0,0)
    return[
        (base_timestamp+ timedelta(minutes=random.randint(0,20000))).strftime("%Y%m%d%H%M")
        for _ in range(size)
    ]
def is_sorted(arr):
    return arr==sorted(arr)
def measure_algorithm(sort_function,data):
    data_copy=data.copy()
    tracemalloc.start()
    start_time=time.perf_counter()
    sorted_data=sort_function(data_copy)
    end_time=time.perf_counter()
    current_memory, peak_memory =tracemalloc.get_traced_memory()
    tracemalloc.stop()
    if not is_sorted(sorted_data):
        raise ValueError(f"{sort_function.__name__} did not sort the data correctly.")
    execution_time= end_time - start_time
    return execution_time,peak_memory
def run_experiment(algorithms,data_generators,sizes,runs):
    time_results={}
    memory_results={}
    for data_name,generator in data_generators.items():
        time_results[data_name]={ algorithm_name: [] for algorithm_name in algorithms }
        memory_results[data_name]={ algorithm_name: [] for algorithm_name in algorithms}

        print(f"\nTesting data type:{data_name}")
        for size in sizes:
            data=generator(size)
            for algorithm_name,algorithm_function in algorithms.items():
                total_time=0
                total_memory=0

                for _ in range(runs):
                    execution_time,peak_memory=measure_algorithm(algorithm_function,data)
                    total_time +=execution_time
                    total_memory +=peak_memory


                average_time=total_time/runs
                average_memory=total_memory/runs
                time_results[data_name][algorithm_name].append(average_time)
                memory_results[data_name][algorithm_name].append(average_memory)

                print(
                    f"{algorithm_name:>8} | Size: {size:>5} | "
                    f"Time: {average_time:.6f} s | Memory: {average_memory:.2f} bytes"
                )

    return time_results, memory_results
def plot_results(results, sizes, algorithms, title_prefix, y_label, output_suffix):
                for data_name in results:
                    plt.figure(figsize=(8,5))

                    for algorithm_name in algorithms:
                        plt.plot(
                            sizes,
                            results[data_name][algorithm_name],
                            marker="o",
                            label=algorithm_name
                        )
                    plt.title(f"{title_prefix} - {data_name} Data")
                    plt.xlabel("dataset size")
                    plt.ylabel(y_label)
                    plt.legend()
                    plt.grid(True)
                    plt.tight_layout()
                    file_name=f"{data_name.lower().replace(' ','_')}_{output_suffix}.png"
                    plt.savefig(file_name)
                    plt.show()

def load_real_world_ev_data(file_path, limit=20000):
    values= []
    with open(file_path,"r", encoding= "utf-8") as file:
        reader= csv.DictReader(file)

        for row in reader:
            value= row.get("Electric Range","").strip()

            if value=="":
                continue
            try:
                values.append(int(float(value)))
            except ValueError:
                continue
            if len(values)>= limit:
                break
    return values
def run_real_world_test():
    file_path = "/Users/shaurya/Documents/SEP/Algocomp/pythonProject1/Electric_Vehicle_Population_Data.csv"

    real_world_sizes = [20000, 50000]
    merge_times = []
    quick_times = []
    merge_memory = []
    quick_memory = []

    print("\nReal-world dataset test: Washington EV Population Data")

    for size in real_world_sizes:
        real_data = load_real_world_ev_data(file_path, limit=size)
        print(f"\nLoaded {len(real_data)} values for real-world test")

        merge_time, merge_mem = measure_algorithm(merge_sort, real_data)
        quick_time, quick_mem = measure_algorithm(quick_sort, real_data)

        merge_times.append(merge_time)
        quick_times.append(quick_time)
        merge_memory.append(merge_mem)
        quick_memory.append(quick_mem)

        print(
            f"Merge Sort | Real-world size: {len(real_data)} | "
            f"Time: {merge_time:.6f} s | Memory: {merge_mem:.2f} bytes"
        )

        print(
            f"Quick Sort | Real-world size: {len(real_data)} | "
            f"Time: {quick_time:.6f} s | Memory: {quick_mem:.2f} bytes"
        )

    bubble_sample = load_real_world_ev_data(file_path, limit=2000)
    bubble_time, bubble_memory = measure_algorithm(bubble_sort, bubble_sample)

    print(
        f"\nBubble Sort | Real-world size: {len(bubble_sample)} | "
        f"Time: {bubble_time:.6f} s | Memory: {bubble_memory:.2f} bytes"
    )

    plot_real_world_results(
        real_world_sizes,
        merge_times,
        quick_times,
        merge_memory,
        quick_memory
    )

def plot_real_world_results(real_world_sizes, merge_times, quick_times, merge_memory, quick_memory):
    plt.figure(figsize=(8,5))
    plt.plot(real_world_sizes,merge_times,marker="o", label="Merge Sort")
    plt.plot(real_world_sizes, quick_times, marker="o", label="Quick Sort")
    plt.title("Execution time comparison- Real world data ")
    plt.xlabel("dataset size")
    plt.ylabel("time(sec)")
    plt.legend()
    plt.grid(True)
    plt.tight_layout()
    plt.savefig("Real_world_time.png")
    plt.show()


    plt.figure(figsize=(8,5))
    plt.plot(real_world_sizes,merge_memory, marker="o", label="Merge sort")
    plt.plot(real_world_sizes, quick_memory, marker="o", label="Quick Sort")
    plt.plot("Memory Usage Comparison- Real world Data")
    plt.xlabel("dataset size")
    plt.ylabel("Memory(bytes)")
    plt.legend()
    plt.grid(True)
    plt.tight_layout()
    plt.savefig("Real_wold_memory.png")
    plt.show()


def main():
    sizes=[500,1000,2000]
    runs=3
    algorithms={
        "Bubble sort":bubble_sort,
        "Merge sort":merge_sort,
        "Quick sort":quick_sort
    }
    data_generators={
        "Random": generate_random_data,
        "Sorted": generate_sorted_data,
        "Reverse": generate_reverse_data,
        "Nearly Sorted": generate_nearly_sorted_data,
        "Timestamp": generate_timestamp_data
    }
    time_results,memory_results = run_experiment (
        algorithms,
        data_generators,
        sizes,
        runs
    )
    plot_results(
        time_results,
        sizes,
        algorithms,
        "execution Time Comparison",
        "Time(seconds)",
        "time"
    )
    plot_results(
        memory_results,
        sizes,
        algorithms,
        "Memory Usage Comparison",
        "Memory (bytes)",
        "memory"
    )
    run_real_world_test()


if __name__ == "__main__":
    main()