task1.py

import time
import random

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

# Selection Sort
def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

# Insertion Sort
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

# Function to generate a random list of integers
def generate_random_list(size):
    return [random.randint(1, 1000) for _ in range(size)]

# Function to measure sorting time
def measure_sorting_time(sort_function, arr):
    start_time = time.time()
    sort_function(arr.copy())
    end_time = time.time()
    return end_time - start_time

# Compare sorting algorithms
def compare_sorting_algorithms():
    sizes = [100, 1000, 5000]  # Different input sizes
    algorithms = {
        "Bubble Sort": bubble_sort,
        "Selection Sort": selection_sort,
        "Insertion Sort": insertion_sort
    }

    for size in sizes:
        print(f"\nInput Size: {size}")
        arr = generate_random_list(size)

        for name, sort_function in algorithms.items():
            time_taken = measure_sorting_time(sort_function, arr)
            print(f"{name}: {time_taken:.6f} seconds")

# Run the comparison
compare_sorting_algorithms()