HOMEWORK SORT CODE
===

import random
import time
import matplotlib.pyplot as plt

# Heap Sort
def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[l] > arr[largest]:
        largest = l

    if r < n and arr[r] > arr[largest]:
        largest = r

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    for i in range(n//2 - 1, -1, -1):
        heapify(arr, n, i)

    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

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

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)

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

    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

    result += left[i:]
    result += right[j:]

    return result

# Quick Sort
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)

# Shell Sort
def shell_sort(arr):
    gap = len(arr) // 2

    while gap > 0:
        for i in range(gap, len(arr)):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2

    return arr

# Timing and plotting
sizes = [50000, 100000, 200000, 300000, 400000, 500000, 1000000]
heap_sort_times = []
merge_sort_times = []
quick_sort_times = []
shell_sort_times = []

for size in sizes:
    data = [random.randint(1, size) for _ in range(size)]

    start_time = time.time()
    heap_sort(data.copy())
    heap_sort_times.append(time.time() - start_time)

    start_time = time.time()
    merge_sort(data.copy())
    merge_sort_times.append(time.time() - start_time)

    start_time = time.time()
    quick_sort(data.copy())
    quick_sort_times.append(time.time() - start_time)

    start_time = time.time
    shell_sort(data.copy())
    shell_sort_times.append(time.time() - start_time)
plt.figure(figsize=(12, 6))
plt.plot(sizes, heap_sort_times, marker='o', label='Heap Sort')
plt.plot(sizes, merge_sort_times, marker='s', label='Merge Sort')
plt.plot(sizes, quick_sort_times, marker='^', label='Quick Sort')
plt.plot(sizes, shell_sort_times, marker='D', label='Shell Sort')

plt.xlabel('Input size')
plt.ylabel('Time (seconds)')
plt.title('Time Complexity Comparison of Sorting Algorithms')
plt.legend()
plt.grid(True)
plt.show()
#This code compares the time complexity of the four sorting algorithms 
# (Heap Sort, Merge Sort, Quick Sort, and Shell Sort) using different input sizes (50,000 to 1,000,000) and plots the results using matplotlib. 
# The graph shows the time taken for each algorithm to sort the random lists of the specified sizes.