main.py

import timeit
import random
n = 100

arr = list(range(1000))
random.shuffle(arr)

ori_arr = arr


def test(arr) -> int:
    """Test the performance of linear search on 1000 elements"""
    target = 777
    for i, value in enumerate(arr):
        if value == target:
            # index found
            return i

def binary_search(arr):
    """Returns the index of target in arr if found, else -1."""
    target = 777
    start = 0
    end = len(arr) - 1

    while start <= end:
        mid = (start + end) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return -1

class HashTable:
    def __init__(self, size=101):
        self.size = size
        self.table = [[] for _ in range(size)]
        self.p = 31
        self.m = 10**9 + 9

    def _hash(self, key):
        """Polynomial rolling hash function for string keys"""
        hash_value = 0
        p_pow = 1
        for char in key:
            hash_value = (hash_value + (ord(char) - ord('a') + 1) * p_pow) % self.m
            p_pow = (p_pow * self.p) % self.m
        return hash_value % self.size

    def put(self, key, value):
        """Insert or update key-value pair"""
        index = self._hash(key)
        bucket = self.table[index]

        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # update existing
                return
        bucket.append((key, value))  # insert new

    def get(self, key):
        """Retrieve value by key, or return -1 if not found"""
        index = self._hash(key)
        bucket = self.table[index]

        for k, v in bucket:
            if k == key:
                return v
        return -1

    def remove(self, key):
        """Remove a key-value pair if it exists"""
        index = self._hash(key)
        bucket = self.table[index]

        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                return True
        return False


def bubble_sort(arr):
    n = len(arr)
    
    for i in range(n):
        # Last i elements are already in place
        for j in range(0, n - i - 1):
            # Swap if elements are in the wrong order
            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

        # Move elements greater than key to one position ahead
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    # Split the array
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    # Merge the sorted halves
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0

    # Compare elements and merge
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    # Add remaining elements
    result.extend(left[i:])
    result.extend(right[j:])
    return result

#array = [...]
import random

def quicksort(arr):
  """
  Sorts a list using Quicksort with a randomized pivot to avoid worst-case performance.
  """
  if len(arr) <= 1:
    return arr
  else:
    # Choose a random element as the pivot. This is the key change.
    pivot = random.choice(arr)
    
    # Partition the list into three parts
    items_less = [x for x in arr if x < pivot]
    pivots = [x for x in arr if x == pivot]
    items_greater = [x for x in arr if x > pivot]
    
    # Recursively sort the sub-lists and combine them.
    return quicksort(items_less) + pivots + quicksort(items_greater)



# Note that the function should be passed to `timeit.timeit` without '()'
# We don't want to call the function, instead we pass it to timeit.
# timeit will call the function (without arguments) and measure the time taken.
print("Time taken (s):", timeit.timeit(lambda: test(arr), number=100))
print("Time taken (s):", timeit.timeit(lambda: binary_search(arr), number=100))
#print("Time taken (s):", timeit.timeit(hash_table, number=n))
print("Time taken (s):", timeit.timeit(lambda: bubble_sort(arr), number=100))
print("Time taken (s):", timeit.timeit(lambda: insertion_sort(arr), number=100))
print("Time taken (s):", timeit.timeit(lambda: merge_sort(arr), number=1000))
print("Time taken (s):", timeit.timeit(lambda: quicksort(arr), number=1000))