Python example of calculating comparison numbers of sorting algorithms

compare.py

from bigO import bigO


class Comparator:
    def __init__(self):
        self.comparisons = 0

    def compare(self, a, b):
        self.comparisons += 1
        if a < b:
            return -1
        if a > b:
            return 1
        return 0


def bubbleSort(array, comp):  # in-place | stable
    """
    Best : O(n) | O(1) Space
    Average : O(n^2) | O(1) Space
    Worst : O(n^2) | O(1) Space
    """
    isSorted = False
    counter = 0
    while not isSorted:
        isSorted = True
        for i in range(len(array) - 1 - counter):
            if comp.compare(array[i], array[i + 1]) == 1:
                array[i], array[i + 1] = array[i + 1], array[i]
                isSorted = False

        counter += 1

    return array


def insertSort(array, comp):  # in-place | stable
    """
    Best O(n) Time | O(1) Space
    Average O(n^2) Time | O(1) Space
    Worst (On^2) Time | O(1) Space
    """
    for i in range(1, len(array)):
        j = i
        while j > 0 and comp.compare(array[j - 1], array[j]) == 1:
            array[j], array[j - 1] = array[j - 1], array[j]
            j -= 1

    return array


def quickSort(array, low=0, high=None, comp=None):
    def insertSort(array, low=1, high=None, comp=None):
        if high is None:
            high = len(array)

        for i in range(low, high):
            j = i
            while j > 0 and comp.compare(array[j - 1], array[j]) == 1:
                array[j], array[j - 1] = array[j - 1], array[j]
                j -= 1

        return array

    if high is None:
        high = len(array) - 1

    while low < high and high - low > 16:
        q = partition(array, low, high, comp)
        quickSort(array, low, q, comp)
        low = q + 1

    return insertSort(array, low + 1, high + 1, comp)


def partition(array, low, high, comp):
    pivot = array[(high + low) // 2]
    # pivot = array[randint(low, high)]
    i = low - 1
    j = high + 1
    while True:
        i += 1
        while comp.compare(pivot, array[i]) == 1:
            i += 1
        j -= 1
        while comp.compare(array[j], pivot) == 1:
            j -= 1

        if i >= j:
            return j

        array[i], array[j] = array[j], array[i]


def countSort(arr, comp):  # stable
    # Time Complexity : O(n) | Space Complexity : O(n)
    minValue = min(arr)
    maxValue = max(arr) - minValue

    buckets = [0 for _ in range(maxValue + 1)]

    for i in arr:
        buckets[i - minValue] += 1

    index = 0
    for i in range(len(buckets)):
        while comp.compare(buckets[i], 0) == 1:
            arr[index] = i + minValue
            index += 1
            buckets[i] -= 1

    return arr


if __name__ == "__main__":
    lib = bigO.bigO()

    arr = lib.genReversedArray(100)
    comp = Comparator()

    comp.comparisons = 0
    bubbleSort(arr, comp)
    print(f"Bubble Sort: {comp.comparisons} times")

    comp.comparisons = 0
    insertSort(arr, comp)
    print(f"Insertion Sort: {comp.comparisons} times")

    comp.comparisons = 0
    quickSort(arr, comp=comp)
    print(f"Quick Sort: {comp.comparisons} times")

    comp.comparisons = 0
    countSort(arr, comp=comp)
    print(f"Count Sort: {comp.comparisons} times")

result.txt

Bubble Sort: 4950 times
Insertion Sort: 99 times
Quick Sort: 399 times
Count Sort: 200 times