test.py

import timeit
from terminaltables import SingleTable


def bubble_sort(arr):
    for i in range(len(arr) - 1):
        for j in range(0, len(arr) - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]


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


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


def merge(a, l, m, r):
    n1, n2 = m - l + 1, r - m
    L = [a[l + i] for i in range(0, n1)]
    R = [a[m + i + 1] for i in range(0, n2)]
    i, j, k = 0, 0, l
    while i < n1 and j < n2:
        a[k] = R[j] if L[i] > R[j] else L[i]
        if L[i] > R[j]:
            j += 1
        else:
            i += 1
        k += 1
    while i < n1:
        a[k] = L[i]
        i += 1
        k += 1
    while j < n2:
        a[k] = R[j]
        j += 1
        k += 1


def merge_sort(a):
    current_size = 1
    while current_size < len(a) - 1:
        left = 0
        while left < len(a) - 1:
            mid = min((left + current_size - 1), (len(a) - 1))
            right = ((2 * current_size + left - 1,len(a) - 1)[2 * current_size+ left - 1 > len(a) - 1])
            merge(a, left, mid, right)
            left = left + current_size * 2
        current_size = 2 * current_size


def count_sort(arr):
    max_value = max(arr)
    counts = [0] * (max_value + 1)
    for item in arr:
        counts[item] += 1
    num_items_before = 0
    for i, count in enumerate(counts):
        counts[i] = num_items_before
        num_items_before += count
    sorted_list = [None] * len(arr)
    for item in arr:
        sorted_list[counts[item]] = item
        counts[item] += 1
    return sorted_list


def partition(arr, l, h):
    i = (l - 1)
    x = arr[h]
    for j in range(l, h):
        if arr[j] <= x:
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[h] = arr[h], arr[i + 1]
    return i + 1


def quick_sort(arr):
    l, h = 0, len(arr) - 1
    size = h - l + 1
    stack = [0] * size
    top = 0
    stack[top] = l
    top = top + 1
    stack[top] = h
    while top >= 0:
        h = stack[top]
        top = top - 1
        l = stack[top]
        top = top - 1
        p = partition(arr, l, h)
        if p - 1 > l:
            top = top + 1
            stack[top] = l
            top = top + 1
            stack[top] = p - 1
        if p + 1 < h:
            top = top + 1
            stack[top] = p + 1
            top = top + 1
            stack[top] = h


def linear_search(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1


def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    mid = 0
    while low <= high:
        mid = (high + low) // 2
        if arr[mid] < x:
            low = mid + 1
        elif arr[mid] > x:
            high = mid - 1
        else:
            return mid
    return -1


sort_algos = ['bubble_sort', 'insertion_sort', 'selection_sort', 'merge_sort', 'count_sort', 'quick_sort']
search_algos = ['linear_search', 'binary_search']
n_values = [10, 100, 1000, 2000, 3000, 5000, 10000]  # 100000

for algo in sort_algos:
    data = [['Number of elements', 'Best', 'Worst', 'Average']]

    for n in n_values:
        setup = f"""from __main__ import {algo}\nfrom random import randint"""
        test = f"""{algo}([randint(0, {n}) for _ in range({n})])"""

        r = timeit.repeat(setup=setup, stmt=test, repeat=4, number=1)
        data.append([n, min(r), max(r), sum(r) / len(r)])

    print(SingleTable(data, algo).table)

n_values.append(100000)
for algo in search_algos:
    data = [['Number of elements', 'Best', 'Worst', 'Average']]

    for n in n_values:
        setup = f"""from __main__ import {algo}\nfrom random import randint"""
        test = f"""{algo}(list(range({n})), randint(0, {n}))"""

        r = timeit.repeat(setup=setup, stmt=test, repeat=4, number=1)
        data.append([n, min(r), max(r), sum(r) / len(r)])

    print(SingleTable(data, algo).table)