pysort.py

import random
from timeit import Timer


def insertion_sort(array):
    for i in range(1, len(array)):
        j = i
        item = array[j]
        while j > 0 and compare(item, array[j - 1]):
            j -= 1
        array[j + 1:i + 1] = array[j:i]
        array[j] = item


def bubble_sort(array):
    for i in range(len(array)):
        swapped = False
        for j in range(i, len(array) - i - 1):
            a = array[j]
            b = array[j + 1]
            if compare(b, a):
                array[j], array[j + 1] = b, a
                swapped = True
        if not swapped:
            break


def selection_sort(array):
    for i in range(len(array) - 1):
        imin = i
        vmin = array[i]
        for j in range(i + 1, len(array)):
            curr = array[j]
            if compare(curr, vmin):
                imin = j
                vmin = curr
        if imin != i:
            array[i], array[imin] = array[imin], array[i]


def merge_sort(array):
    if len(array) <= 1:
        return
    mid = len(array) // 2
    left = array[:mid]
    right = array[mid:]
    merge_sort(left)
    merge_sort(right)
    imain = ileft = iright = 0
    while ileft < len(left) and iright < len(right):
        if not compare(right[iright], left[ileft]):
            array[imain] = left[ileft]
            ileft += 1
        else:
            array[imain] = right[iright]
            iright += 1
        imain += 1
    leftcopy = imain + len(left) - ileft
    array[imain:leftcopy] = left[ileft:]
    array[leftcopy:] = right[iright:]


def quick_sort(array):
    def sort_range(main_array, low, high):
        pivot = main_array[(low + high) // 2]
        ileft, iright = low, high
        while ileft <= iright:
            while compare(main_array[ileft], pivot):
                ileft += 1
            while compare(pivot, main_array[iright]):
                iright -= 1
            if ileft > iright:
                break
            main_array[ileft], main_array[iright] = main_array[iright], main_array[ileft]
            ileft += 1
            iright -= 1
        if low < iright:
            sort_range(main_array, low, iright)
        if ileft < high:
            sort_range(main_array, ileft, high)

    sort_range(array, 0, len(array) - 1)


def compare(a, b):
    return a < b


def random_list(length, min_value, max_value):
    return [int(min_value + max_value * random.random()) for x in range(length)]


def ascending_list(length, min_value, max_value):
    return [int(min_value + x * (max_value - min_value) / length) for x in range(length)]


def descending_list(length, min_value, max_value):
    return [int(min_value + (length - x - 1) * (max_value - min_value) / length) for x in range(length)]


def assert_sorted(array):
    for i in range(len(array) - 1):
        if compare(array[i + 1], array[i]):
            raise Exception("Not sorted!")


def sort_single(sorter, generator, length, trials):
    array = generator(length, 0, 100)
    t = Timer(lambda: sorter(array))
    print(sorter.__name__ + ":\t" + str(t.timeit(number=trials)))
    assert_sorted(array)


def sort_batch(sorters, generator, length, trials):
    print("List:", generator.__name__)
    print("Length:", length)
    print("Trials:", trials)
    print("------------------------------")
    for sorter in sorters:
        sort_single(sorter, generator, length, trials)
    print("------------------------------")


def main():
    algorithms = (insertion_sort, bubble_sort, selection_sort, merge_sort, quick_sort)
    length = 10000
    trials = 1
    sort_batch(algorithms, ascending_list, length, trials)
    sort_batch(algorithms, descending_list, length, trials)
    sort_batch(algorithms, random_list, length, trials)
    print("Done!")


if __name__ == "__main__":
    main()