import time
import math
import random
import pandas as pd

# --- Search algorithms ---
def linear_search(arr, target):
    for i, value in enumerate(arr):
        if value == target:
            return i
    return -1

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    while left <= right:
        middle = (left + right) // 2
        if target == arr[middle]:
            return middle
        elif target < arr[middle]:
            right = middle - 1
        else:
            left = middle + 1
    return -1

def jump_search(arr, target):
    n = len(arr)
    step = int(math.sqrt(n))
    prev = 0
    while prev < n and arr[min(step, n)-1] < target:
        prev = step
        step += int(math.sqrt(n))
        if prev >= n:
            return -1
    while prev < min(step, n) and arr[prev] < target:
        prev += 1
        if prev == n:
            return -1
    if prev < n and arr[prev] == target:
        return prev
    return -1

# --- Insertion sort ---
def insertion_sort(arr):
    for j in range(1, len(arr)):
        key = arr[j]
        i = j - 1
        while i >= 0 and arr[i] > key:
            arr[i + 1] = arr[i]
            i = i - 1
        arr[i + 1] = key
    return arr

# --- Benchmark helpers ---
def benchmark_search_with_sort(sort_func, search_func, original_arr, target, repeats=100):
    sorting_time = 0
    search_time = 0
    for _ in range(repeats):
        arr = original_arr[:]

        # Sortér array
        start_sort = time.perf_counter()
        sorted_arr = sort_func(arr) if sort_func != sorted else sorted(arr)
        sorting_time += time.perf_counter() - start_sort

        # Søg i det sorterede array
        start_search = time.perf_counter()
        search_func(sorted_arr, target)
        search_time += time.perf_counter() - start_search

    # Gennemsnit i millisekunder
    sorting_time_avg = (sorting_time / repeats) * 1000
    search_time_avg = (search_time / repeats) * 1000
    return round(search_time_avg, 6), round(sorting_time_avg, 6), round(search_time_avg + sorting_time_avg, 6)

def benchmark(func, arr, target, repeats=100):
    total = 0
    for _ in range(repeats):
        arr_copy = arr[:]
        start = time.perf_counter()
        func(arr_copy, target)
        total += time.perf_counter() - start

    avg_time = (total / repeats) * 1000  # Til millisekunder
    return round(avg_time, 6), 0.0, round(avg_time, 6)

# --- Benchmarking ---
sizes = [1, 8, 20, 100, 1000, 5000, 10000]
data = []

for size in sizes:
    arr = random.sample(range(size * 3), size)
    target = size * 3 + 1  # Not in array

    for name, func, sort_func in [
        ("Lineær Søgning (Usorteret)", linear_search, None),
        ("Binær Søgning + Insertion Sort", binary_search, insertion_sort),
        ("Binær Søgning + TimSort", binary_search, sorted),
        ("Jump-Søgning + Insertion Sort", jump_search, insertion_sort),
        ("Jump-Søgning + TimSort", jump_search, sorted),
    ]:
        if sort_func:
            runtime, sorting_time, total_time = benchmark_search_with_sort(sort_func, func, arr, target)
        else:
            runtime, sorting_time, total_time = benchmark(func, arr, target)

        data.append({
            "Søgealgoritme": name,
            "Inputmængde (n)": size,
            "Køretid (ms)": runtime,
            "Sorteringstid (ms)": sorting_time,
            "Akk. tid (ms)": total_time,
        })

df = pd.DataFrame(data)
df.to_csv("usorteret_algoritmetest.csv", index=False)