Python Example 3

import random
import time

# Kaizer here. I implemented and compared different sorting algorithms using 3 main ones. quicksort, mergesort, and heapsort, in terms of performance.
# function to print an array
def print_array(arr):
    print(*arr)

# quicksort implementation
def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quicksort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quicksort(arr, low, pi - 1)
        quicksort(arr, pi + 1, high)

# mergesort implementation
def merge(arr, left, mid, right):
    n1 = mid - left + 1
    n2 = right - mid

    L = arr[left:left+n1]
    R = arr[mid+1:mid+1+n2]

    i = j = 0
    k = left

    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1

    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1

    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1

def mergesort(arr, left, right):
    if left < right:
        mid = (left + right) // 2
        mergesort(arr, left, mid)
        mergesort(arr, mid + 1, right)
        merge(arr, left, mid, right)

# heapsort implementation
def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

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

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

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

def heapsort(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[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

# function to measure and compare sorting times
def compare_sorts(arr):
    arr1 = arr.copy()
    arr2 = arr.copy()
    arr3 = arr.copy()

    start = time.time()
    quicksort(arr1, 0, len(arr1) - 1)
    end = time.time()
    quicksort_time = end - start
    print(f"Quicksort time: {quicksort_time:.6f} seconds")

    start = time.time()
    mergesort(arr2, 0, len(arr2) - 1)
    end = time.time()
    mergesort_time = end - start
    print(f"Mergesort time: {mergesort_time:.6f} seconds")

    start = time.time()
    heapsort(arr3)
    end = time.time()
    heapsort_time = end - start
    print(f"Heapsort time: {heapsort_time:.6f} seconds")

if __name__ == "__main__":
    arr = [12, 11, 13, 5, 6, 7]
    print("Original array:", end=" ")
    print_array(arr)

    compare_sorts(arr)